[백준 4097번] 수익 (C++)

문제링크 : https://www.acmicpc.net/problem/4097

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
int arr[250001];
int dp[250001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    while(true)
    {
        int result = -MAX;
        cin >> N;
        if(N==0) break;

        for(int i=0; i<N; i++) cin >> arr[i];
        dp[0] = arr[0];
        for(int i=1; i<N; i++) 
        {
            dp[i] = max(dp[i-1]+arr[i], arr[i]); //직전 구간 및 새 시작점 체크
            result = max(dp[i], result);
        }
        cout << result << "\n";
    }

    return 0;
}

 

구간이 비어있으면 안되므로 직전 값에 더하여 계속해서 dp에 누적합을 갱신해준다.

이때 직전 합 + 현재 값이 현재 값보다 작다면 현재 값을 새로운 구간의 시작점으로 다시 누적합을 구하게 된다.

이렇게 구한 구간의 누적합 중 가장 큰 값을 따로 출력해주면 된다.