累積和ですぐ!!
問題概要
個の整数からなる数列
と、整数
が与えられる。
数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。
制約
考えたこと
「数列の連続する部分の総和」は累積和を求めることで管理できる。累積和については以下の記事を参照。
今回も、 の累積和
を次のように定義する。
- ...
をあらかじめ計算しておく。この作業は
でできる。この
を用いると
の区間
の総和は
というふうに簡潔に表せる。よって今回の問題は
を動かしていったときの
の値の最大値
を求めれば OK。計算量は 。
コード
#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; }