[BOJ/백준][Gold5] 13398 : 연속합 2 (C++)

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

13398번: 연속합 2

 

 

[난이도] Gold5
[유형] DP

[풀이]
dp[i][k] (i:0~N-1, k:0,1)
dp[i][0] : 숫자 한개를 제거하지 않은 i번째로 끝나는 수열의 합 중 최댓값
dp[i][1] : 숫자 한개를 제거한 i번째로 끝나는 수열의 합 중 최댓값

k=0을 구하는 법 : dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i]
숫자를 제거하지 않을 것이므로 dp[i-1]에 a[i]를 이어붙이면 된다. 단, dp[i-1]이 음수인 경우에는
dp[i-1]을 합치는 것은 합을 줄어들게 하므로 a[i]만 dp[i][0]으로 설정한다.

k=1을 구하는 법 : dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]);
dp[i-1][0]은 a[i] (제일 오른쪽)을 제거하는 경우인데, 아직 숫자가 제거되지 않았어야 하므로 dp[i-1][0]이다.
dp[i-1][1]+a[i]는 이미 숫자가 제거된 dp[i-1][1]에 a[i]를 이어붙이는 케이스이다.

위의 방법으로 O(N)에 해결이 가능하다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[100000],dp[100000][2],ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    dp[0][0]=a[0];
    ans=a[0];
    for(int i=1;i<N;i++){
        dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i];
        dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]); 
        ans=max(dp[i][0],ans);
        ans=max(dp[i][1],ans);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/13398.cpp