aoj0516:Maximum Sum

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516

解法

累積和をとって、考えられるN-K+1個の区間をそれぞれO(1)で見ていった。全体でO(N)。

プログラミングを始めたばっかりのころは尺取法で解いたけど、今回はバグへの恐怖からか累積和を使った。

コード

#include<bits/stdc++.h>
using namespace std;

int N,K;
int a[100001];

void solve(){
    for(int i=0;i<N;i++){
        scanf("%d",&a[i+1]);
        a[i+1]+=a[i];
    }
    int ma=0;
    for(int i=K;i<=N;i++)ma=max(ma,a[i]-a[i-K]);
    printf("%d\n",ma);
}
int main(){
    while(scanf("%d%d",&N,&K),N||K)solve();
}