けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2007 A - 最大の和 (AOJ 0516, 難易度 4)

JOI JOI本選 JOI難易度4 累積和 AOJ AtCoder

累積和ですぐ！！

問題概要

N 個の整数からなる数列 A_{0}, \dots, A_{N-1} と、整数 K が与えられる。

数列から連続する K 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。

制約

  • 1 \le K \le N \le 10^{5}

考えたこと

「数列の連続する部分の総和」は累積和を求めることで管理できる。累積和については以下の記事を参照。

qiita.com

今回も、 A の累積和 S を次のように定義する。

  • S_{0} = 0
  • S_{1} = A_{0}
  • S_{2} = A_{0} + A_{1}
  • S_{3} = A_{0} + A_{1} + A_{2}
  • ...
  • S_{N} = A_{0} + A_{1} + A_{2} + \dots + A_{N-1}

S をあらかじめ計算しておく。この作業は O(N) でできる。この S を用いると A の区間 \lbrack l, r) の総和は

A_{l} + A_{l+1} + \dots + A_{r-1} = S_{r} - S_{l}

というふうに簡潔に表せる。よって今回の問題は

  • i を動かしていったときの
  • S_{i+K} - S_{i} の値の最大値

を求めれば OK。計算量は O(N)。

コード

#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値

int main() {
    // 入力
    int N, K; cin >> N >> K;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
        
    // 累積和を前計算
    vector<int> s(N+1, 0);
    for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i];
    
    // 答えを求める
    long long res = -INF; // 最初は無限小の値に初期化しておく
    for (int i = 0; i <= N-K; ++i) {
        long long val = s[K+i] - s[i];
        if (res < val) res = val;
    }
    cout << res << endl;
}