[백준 1912번] [동적 계획법] 연속합

Approach

Let dp[i] : Continuous maximum sum considering i'th element

If dp[i - 1] value is negative, dp[i] could be maximize by throwing previous continuous sum.

On the oher hand, dp[i] could be maximized by along previous continuous sum.

 

So, Recurrence relation could be represented by

$$ dp[i] \begin{cases} v[i] & \mbox{(if dp[i - 1] is negative)} \\ v[i] + dp[i - 1] & \mbox{(if dp[i - 1] is positive)} \end{cases} $$

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

//i번째까지 고려했을 떄의 max값
int dp[100001];

int main(void){
    fastio;
    int n;
    cin >> n;

    int v_1;
    cin >> v_1;
    dp[1] = v_1;

    for(int i = 2; i <= n; i++){
        int v;
        cin >> v;

        if(dp[i - 1] > 0){
            dp[i] = dp[i - 1] + v;
        }
        else{
            dp[i] = v;
        }
    }
    int max_value = -987654321;

    for(int i = 1; i <= n; i++){
        if(dp[i] > max_value){
            max_value = dp[i];
        }
    }

    cout << max_value << "\n";
    return 0;
}