2559: 수열

[minsoo0715]

2559: 수열

소스 코드

아이디어

1차원 누적합 배열을 만들면 s[2] - s[1] = v[2]이고 s[3] - s[1] = v[3] + v[2]이다.
따라서 K일 동안의 합은 s[i] - s[i-K]로 나타낼 수 있다. 이에 대해서 최댓값을 구하면 된다.

구현

누적합을 구해서 sum[i] - sum[i-K]가 최대가 되는 구간을 구한다.

for(int i = K; i <= N; ++i) {
    max = std::max(max, s[i]-s[i-K]);
}