[백준][DP] 연속합2

1. 문제 주소

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

13398번: 연속합 2

2. 문제

left_dp[i]에는 0번 항부터 i번 항까지의 수를 더한 값을 입력을 하였고 right_dp[i]에는 i번 항부터 마지막 항까지의 수를 더한 값을 입력을 해주었다. 그리고 left_dp[i-1] + right_dp[i+1]은 i번째 수를 제외한 합이 되므로 이를 이용하여 최댓값을 구하는 코드를 작성하였다.

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> series(n);
    for (int i = 0; i < n; i++) {
        cin >> series[i];
    }
 
    vector<int> left_dp(n);
    vector<int> right_dp(n);
 
    for (int i = 0; i < n; i++) {
        left_dp[i] = series[i];
        if (i > 0 && left_dp[i] < left_dp[i - 1] + series[i])
            left_dp[i] = left_dp[i - 1] + series[i];
    }
 
    for (int i = n - 1; i >= 0; i--) {
        right_dp[i] = series[i];
        if (i < n - 1 && right_dp[i] < right_dp[i + 1] + series[i])
            right_dp[i] = right_dp[i + 1] + series[i];
    }
 
    int max_value = left_dp[0];
    for (int i = 1; i < n; i++) {
        max_value = max(max_value, left_dp[i]);
    }
    for (int i = 1; i < n - 1; i++) {
        max_value = max(max_value, left_dp[i - 1] + right_dp[i + 1]);
    }
    cout << max_value << '\n';
    return 0;    
}