[BOJ/C++] 13398 연속합 2

동적 계획법을 이용해 문제를 해결할 수 있습니다.

우선 $DP[N]$은 0부터 N을 포함하여 연속해서 값을 선택했을 때의 최댓값 입니다.

이 때 하나의 값을 삭제하여 최댓값을 만들수도 있습니다.

왼쪽에서의 연속된 합 배열 L과 오른쪽에서의 연속된 합 배열 R을 통하여 1개를 제거하는 효과를 볼 수 있습니다

$L[i-1] + R[i+1]$

초기의 최댓값은 0~N까지 하나도 제거하지 않았을 때의 최댓값으로 설정합니다.

 // boj g5 13398
// 연속합 2
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> A, L, R;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    A.resize(N);
    L.resize(N);
    R.resize(N);


    for (int i = 0; i < N; i++)
        cin >> A[i];

    L[0] = A[0];
    int result = L[0];
    for(int i=1; i<N; i++)
    {
        L[i] = max(A[i], L[i - 1] + A[i]);
        result = max(L[i], result);
    }

    R[N-1] = A[N - 1];
    for(int i=N-2; i>=0; i--)
    {
        R[i] = max(A[i], R[i + 1] + A[i]);
    }


    for(int i=1; i<N-1; i++)
    {
        result = max(result, L[i - 1] + R[i + 1]);
    }

    cout << result;
    

    return 0;
}