累積和の累積 max
問題概要
数列 が与えられます。 この数列は負の要素を含むかもしれません。
数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。
- 正の向きに
進む。
- 正の向きに
進み、正の向きに
進む。
- 正の向きに
進み、正の向きに
進み、正の向きに
進む。
- ⋮
- 正の向きに
進み、正の向きに
進み、...、正の向きに
進む。
動作開始時から終了時までのロボットの座標の最大値を求めてください。
制約
考えたこと
加算する要素の個数は 通りあるので、愚直に足して行ったのでは間に合わない。
そこで、次のデータを持つことにしよう。
:=
の総和
:=
の最大値
はいわゆる「累積和」で、
は「累積和の累積 max」とでも呼ぶべきものとなっている。これらの計算は
でできる。これを用いると、次のように求められる。
- 最初の
回の操作を終えたあとの位置を
とする
に
を足していったときの
- 結果は、
となる
- その過程での座標の最大値は、
となる
- 結果は、
以上の操作を各 に対して実施していく。全部合わせて計算量は
となる。
コード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> A(N), S(N+1, 0), M(N+1, 0); for (int i = 0; i < N; ++i) { cin >> A[i]; S[i+1] = S[i] + A[i]; M[i+1] = max(M[i], S[i+1]); } long long res = 0, cur = 0; for (int i = 0; i < N; ++i) { res = max(res, cur + M[i+1]); cur += S[i+1]; } cout << res << endl; }