[Jungol] 정올 2497 수열

출처: http://www.hancom.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1758&sca=50

 Input 

10 2

3 -2 -4 -9 0 3 7 13 8 -3

 

 Output 

21

 

psum[i] = 첫번째 원소부터 i번 원소까지의 구간합

▶ A[i] = psum[i] - psum[i-1]

    ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4

▶ (K ≤ i) K 길이의 구간 합 = psum[i] - psum[i - K]

    ex) 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8

          psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지의 합) = (8 ~ 9까지의 합)　

---

#include <stdio.h>
const int LM = 100005;
int N, K, A[LM], psum[LM];
int ans = -(int) 1e9;
void input() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", A + i);
        psum[i] = psum[i - 1] + A[i];
    }
}
 
void process() {
    int i, sum = 0;
    for (i = 1; i <= N; ++i) {
        sum += A[i];
        if (i >= K) {
            sum = psum[i] - psum[i - K];
            if (ans < sum) ans = sum;
        }
    }
}
 
int main(void) {
    // freopen("input.txt", "r", stdin);
    input();
    process();
    printf("%d\n", ans);
}