연속합 2 (중요!)

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

13398번: 연속합 2

숫자를 빼고 그 때마다 연속합을 구하면 시간 초과 날 게 뻔하다!!

숫자를 기준으로 나누자!

d[i] = i번째에서 끝나는 연속합

d2[i] = i번째에서 시작하는 연속합

#include <iostream>
#include <algorithm>
 
int a[100004];
int d[100004];
int d2[100004];
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    d[1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        d[i] = max(d[i - 1] + a[i], a[i]);
    }
 
    d2[n] = a[n];
    for (int i = n-1; i >= 1; i--)
    {
        d2[i] = max(d2[i + 1] + a[i], a[i]);
    }
//수를 제거하지 않아도 되므로!
    int ans = d[1];
    for (int i = 1; i <= n; i++)
    {
        if (ans < d[i])
            ans = d[i];
    }
 
    // 뺀 거 비교
    for (int i = 2; i <= n - 1; i++)
    {
        if (ans < d[i - 1] + d2[i + 1])
            ans = d[i - 1] + d2[i + 1];
    }
 
    cout << ans << '\n';
}