구간합 유형의 문제로 psum[]으로 풀이하면 된다.
(psum은 prefix sum을 의미한다)

주의할점은 입력의 n,k의 크기가 2~100000 이므로, O(n^2)이 되는 알고리즘은 사용하면 안된다. O(nlogn)까지만 사용 가능하다.

또한 최댓값을 구해야하는데, 최댓값은 항상 최솟값으로 구하고 / 최솟값은 항상 최댓값으로 구해야함을 유념하자.
최솟값은 -> 최악의 경우 100000*(-100)=-10000000 인데, 혹시 모르니 -10000004 으로 두는 것이 바람직하다.

또한 psum[]은 첫 번째 수를 인덱스 1로 사용하므로 배열의 크기를 100001 으로 설정해준다.

우선, 수를 입력받아서 psum[]에 누적한다
이후 -> max(a,b)를 사용하여 최댓값을 뽑아주고 출력한다.

결과적으로 시간 복잡도가 O(n) 이되어 시간 초과 오류를 피할 수 있다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;
int psum[100001];
int res = -10000004;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N,k,input;
    cin >> N >> k;
    for(int i=1;i<N+1; i++) {
        cin >> input;
        psum[i]=psum[i-1]+input;
    }
    for(int i=0;i<N-k+1;i++) {
        res = max(res, psum[i+k]-psum[i]);
    }
    cout << res;
    return 0;
}

2. 오답노트

(1) 구간합 유형임을 빠르게 캐치하자

이번에 다행히 구간합 유형임을 빠르게 캐치해서 조금 수월하게 풀 수 있었던 것 같다.

(2) psum[] 을 확실히 외우자

int psum[n+1];
for(int i=1;i<n;i++) {
	cin >> input;
    psum[i]=psum[i-1]+input;
}

이 템플릿을 잘 외워두자.

그리고 psum[]의 경우 인덱스 0은 사용하지않는다.
1번째 수 를 index 1로 사용함을 잊지말자

(3) 최댓값, 최솟값 구하기

최댓값은 최솟값에서 시작해서 구하고,
최솟값은 최댓값에서 시작해서 구한다.

//최솟값 구하기
res = 문제상 나올 수 있는 가장 큰 수 + 1
for(int n:arr) res=min(res, n);
//최댓값 구하기
res = 문제상 나올 수 있는 가장 작은 수 - 1
for(int n:arr) res=max(res, n);