문제

image.png

image.png

풀이

배열 중 한개를 버리는 경우와, 그렇지 않은 경우로 나눠진다. 2차원 배열로 dp 표현

dp[n][0] = n까지의 연속합, 버린 경우는 없다
dp[n][1] = n까지의 연속합, 1개를 버린 경우

버리지 않는 경우에는, dp[n-1][0] + a[n]과 a[n]을 비교해서 큰 값을 선택하면 된다.
버리는 경우에는, n-1번째 까지는 버리지 않은경우에서 현재 값을 버리는 경우 (dp[n-1][0]) 가 있고 n-1번째 까지 1개를 버려서 현재값은 무조건 선택해야하는 경우가 있다.(dp[n-1][1] + a[n])

a 10 -4 3 1 5 6 -35 12 21 -1
dp[n][0] 10 6 9 10 15 21 -14 12 33 32
dp[n][1] 10 10 13 14 19 25 21 33 54 53

코드

#include<stdio.h>
#include<algorithm>
#define MAX 1000001
using namespace std;
int dp[MAX][2];
int a[MAX];
int main() {

    int n,ans = -2147000000;
    scanf("%d",&n);

    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }
    dp[1][0] = a[1];
    dp[1][1] = a[1];

    for(int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i-1][0] + a[i], a[i]);
        dp[i][1] = max(dp[i-1][0], dp[i-1][1] + a[i]);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= 1; j++) {
            ans = max(ans,dp[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}