Maximum Sum - kyoupuro @ ウィキ

0516 : Maximum Sum

問題文

解説

長さnの数列の中で、連続した長さkの数列の和の最大値を出力する。
sum(i) = a[0] + a[1] + ・・・ + a[i]とすると、
a[s] + a[s+1] + ・・・ + a[t-1] = sum(t) - sum(s)となる。

まず、0番目からi番目までの整数の和を配列に格納していく。
その後、「i+k」番目の要素から「i」番目の要素を引けば、「i～k-1」番目の整数の和を得ることができる。

プログラム

C

C++

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
 
int main() {
    int n, k, a;
    while (cin >> n >> k, n || k) {
        int sum = 0;
        vector<int> s;
        for (int i = 0; i < n; i++) {
            cin >> a;
            sum += a;
            s.push_back(sum);
        }
 
        int max = INT_MIN;
        for (int i = 0; i < n-k; i++) {
            if (max < s[i+k] - s[i]) max = s[i+k] - s[i];
        }
 
        cout << max << endl;
    }
    return 0;
}

Java