[백준]연속합 2(13398)

문제 링크 : [백준]연속합 2(13398)

문제 설명

N개의 수열이 주어질 때, 연속된 구간의 합 중 최대값을 구하세요.
단, 연속합을 구할 때, 하나의 수를 제외하고 연속합을 구할 수 있습니다.

입력

N(수열의 갯수, 1 <= N <= 100,000)
V_i(각 수열의 값, -1,000 <= V_i <= 1,000)

10
10 -4 3 1 5 6 -35 12 21 -1

출력

54

카테고리

#DP

시간 복잡도 상한

O(NlogN)

해결 방법

1. 중간에 한개를 빼는 조건이 없다면, 현재 위치로 끝나는 최대 연속합을 구하면 됩니다.
   1-1. D[i] = max(D[i-1] + V[i], V[i])
2. 그러나 중간에 하나를 뺄 수 있는 경우가 있기 때문에 특별한 조치가 필요합니다.
3. DP 배열 하나를 더 만들어야합니다.
4. E[i]에다가 오른쪽에서 시작하여 왼쪽으로 진행하면서 i로 끝나는 최대 연속합을 구합니다. 쉽게 말해, D[i]와 반대 방향으로 연속합을 구합니다.
   4-1. E[i] = max(E[i+1] + V[i],V[i])
5. i를 기준으로, 왼쪽 D값과 오른쪽 E값을 구하여, i를 뺀 왼쪽 오른쪽 연속 구간합들의 최대값을 구합니다.
6. answer = for(i=1;i<=N;i++)max(answer, D[i-1] + E[i+1])
7. 단, 하나도 안뺴도 되기 때문에, 그 값들에 대한 처리도 해줍니다.

시간복잡도

O(N)

코드

#include<iostream>
#include<algorithm>
#define N 100000
using namespace std;
int n,d[N],e[N],f[N],i,s;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(i=0;i<n;i++)cin>>d[i];
    e[0]=d[0];f[n-1]=d[n-1];
    s=max(e[0],f[n-1]);
    for(i=1;i<n;i++){
        e[i]=max(e[i-1]+d[i],d[i]);
        f[n-i-1]=max(f[n-i]+d[n-i-1],d[n-i-1]);
        s=max(s,max(e[i],f[n-i-1]));
    }
    for(i=1;i<n-1;i++)s=max(s,e[i-1]+f[i+1]);
    cout<<s;
}