13398. 연속합2

1. 해결방법

• Dynamic Programming
• DP[n] : n번째 수를 포함했을 때 연속합의 최대합을 의미.
• DP_left[n] : n번째 수를 포함했을 때 n 기준 왼쪽에 있는 연속합의 최대합을 의미.
• DP_right[n] : n번째 수를 포함했을 때 n 기준 오른쪽에 있는 연속합의 최대합을 의미.

 

• 문제의 조건에는 "수열에서 수를 하나 제거할 수 있다 (제거하지 않아도 된다)" 라고 하였기 때문에, n을 기준으로 왼쪽과 오른쪽에 있는 연속합을 더할 수 있다.
• DP_left[n - 1] + DP_right[n + 1] 
• 수를 제거하지 않았을 때의 연속합의 최대합과, 수를 하나 제거했을 때의 연속합의 최대합을 비교하면 된다.

2. Solution

#include <iostream>

#define MAX_ 100000 + 1
#define endl "\n"

typedef long long ll;

using namespace std;

int n;
int arr[MAX_];
ll DP_left[MAX_];
ll DP_right[MAX_];
ll answer;

ll MAX(ll A, ll B) {return A > B ? A : B;}

void Input()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
}

void Initial()
{
    DP_left[1] = arr[1];
    DP_right[n] = arr[n];

    answer = DP_left[1];    // 연속된 수 중 가장 큰 값
}

void Solution()
{
    for(int i = 2; i <= n; i++)
    {
        DP_left[i] = MAX(DP_left[i - 1] + arr[i], arr[i]);
        answer = MAX(answer, DP_left[i]);
    }
    for(int i = n - 1; i >= 1; i --)
    {
        DP_right[i] = MAX(DP_right[i + 1] + arr[i], arr[i]);
    }

    for(int i = 2; i <= n - 1; i++)
    {
        answer = MAX(answer, DP_left[i - 1] + DP_right[i + 1]);
    }

    cout << answer << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Initial();
    Solution();

    return 0;
}