백준 c++ 13398 - 연속합 2

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

13398번: 연속합 2

필자 처음 사고과정 :

DP문제가 이 문제의 해결 KEY다 -> D[idx] 마다 최댓값을 저장하려 했지만 문제의 조건중에 자유롭게 하나의 수를 제거할 수 있다. 라는 이유로 이 방식은 포기했다.

해결과정 : 

 

이 문제의 핵심은 위의 그림처럼 X표시 되는 모든 구간을 조사하여 최댓값이 되는 값을 구해야 되는 문제다.
이러한 이유로 L벡터와 R벡터를 만들었다. 
L 벡터에는 왼쪽부터 시작하여 배열의 마지막 원소까지 최댓값을 넣어 주고 R 벡터에는 오른쪽부터 시작하여 배열의 처음 원소까지 최댓값을 넣어준다.

마지막 L[i-1]과 R[i+1]의 값을 더해주면 X표시의 값을 제외했고 그 값을 비교해서 최댓값을 구해주면 해결된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, Answer;
int Arr[MAX];
int Left_Sum[MAX];
int Right_Sum[MAX];
 
int Max(int A, int B) { return A > B ? A : B; }
    
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    if (N == 1)
    {
        cout << Arr[1] << endl;
        return;
    }
 
    Left_Sum[1] = Arr[1];
    Answer = Left_Sum[1];
    for(int i = 2; i <= N; i++)    
    { 
        Left_Sum[i] = Max(Arr[i], Left_Sum[i - 1] + Arr[i]);
        Answer = Max(Answer, Left_Sum[i]);
    }
    Right_Sum[N] = Arr[N];
    for (int i = N - 1; i >= 1; i--)
    {
        Right_Sum[i] = Max(Arr[i], Right_Sum[i + 1] + Arr[i]);
    }
    
    for (int i = 2; i <= N - 1; i++) Answer = Max(Answer, Left_Sum[i - 1] + Right_Sum[i + 1]);
    
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}