[BAE/<JOON> 문제풀이] 1912. 연속합 (DP.009)

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

개인적으론 계단이나 와인문제보단 쉬운 문제 같다.

 

이전 숫자까지의 최대합을 계산하고 계속 더해나갈 것인지 아니면, 끊고 새로운 최댓값을 찾을 것인지만 결정하면 된다.

 

(이전 문제들처럼 이전 노드의 상태를 검사할 필요가 없었다.)

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> arr;
    vector<int> dp;
    arr.resize(n + 2);
    dp.resize(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    dp[1] = arr[1];
    int max = arr[1];
    dp[n + 1] = 0;
    arr[n + 1] = 0;
    
    for (int i = 2; i <= n + 1; i++) {        
        int R = (arr[i - 1] > dp[i - 1] ? arr[i - 1] : dp[i - 1]) + arr[i];
        dp[i] = R;
        if (max < R) max = R;      
        if (max < arr[i] && i != n + 1) max = arr[i];
    }    

    /*for (int i = 1; i <= n + 1; i++) {
        cout << dp[i] << " " << arr[i] << endl;
    }

    cout << endl;*/

    cout << max << endl;

    return 0;
}