백준 13398: 연속합 2

#include <iostream>
#include <algorithm>
#include <stack>
long long d[100050];
int num[100050];
long long dr[100050];
int rev_num[100050];
 
using namespace std;
int main()
{
    stack<int> reverse_val;
    int input;
    cin >> input;
    for (int i = 1; i <= input; ++i)
    {
        cin >> num[i];
    }
    d[1] = num[1];
    for (int i = 1; i <= input; ++i)
    {
        d[i] = d[i - 1] + num[i];
        //새로 부분합을 시작하는 경우
        if (d[i] < num[i])
            d[i] = num[i];
    }
    //수열을 뒤집은 후 부분열을 구한다.
    for (int i = 1;i <= input; ++i)
        reverse_val.push(num[i]);
    for (int i = 1; i <= input; ++i)
    {
        rev_num[i] = reverse_val.top();
        reverse_val.pop();
    }
 
    dr[1] = rev_num[1];
    for (int i = 1; i <= input; ++i)
    {
        dr[i] = dr[i - 1] + rev_num[i];
        //새로 부분합을 시작하는 경우
        if (dr[i] < rev_num[i])
            dr[i] = rev_num[i];
    }
    //제거하지 않았을 경우의 정답
    long long ans = d[1]; 
    for (int i = 1;i <= input; ++i)
        ans = max(ans, d[i]);
    //제거 했을 경우의 정답
    for (int k = 1; k <= input; ++k)
        ans = max(ans, d[k - 1] + dr[input - k]);
    cout << ans << endl;
    return 0;
}