백준 2208 - 보석 줍기

www.acmicpc.net/problem/2208

풀이

배열의 prefix sum을 계산해준다.

 

n개의 보석만큼 반복문을 돌리는데 다음 계산의 최댓값이 정답이 된다.

 

보석 i번째까지 전부 먹었을 때 누적합 - 이전 구간에서 최대로 손해를 입는 누적합

 

구현에서는 이전 구간에서 최대로 손해를 입는 누적합을 저장하기 위해 별도의 변수를 두었다.

 

전체 코드

#include <bits/stdc++.h>
     
using namespace std;
 
int ar[100001];
int prefix[100001];
int n, m;
int res;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> ar[i];
        prefix[i] = prefix[i - 1] + ar[i];
    }
 
    int val = 0;
 
    for (int i = m; i <= n; ++i)
        res = max(res, prefix[i] - (val = min(prefix[i - m], val)));
 
    cout << res;
}