2559: 수열

어떤 문제인가?

$i$와 $j$의 차가 일정할 때($j-i=k)$, $i$~$j$번째 구간 합들 중 최댓값을 구하라.

시행착오 횟수

한 번에 성공.

1차 시도: AC

11659번의 응용 문제로 보인다. 최댓값 구하기 + 구간 합 원리만 적용하면 쉽게 풀 수 있다.

#include <stdio.h>

int T[100001];

int main() {
    int N,K,M=-10000000,S,f,e,t;
    scanf("%d%d", &N, &K);
    
    for(int i=1; i<=N; i++) {
        scanf("%d", &t);
        T[i] = T[i-1] + t;
    }
    
    for(int i=K; i<=N; i++)
        M = M < T[i]-T[i-K] ? T[i]-T[i-K] : M;
    
    printf("%d\n", M);
}

다른 분들의 풀이

내 풀이와 매우 유사하므로 생략한다.