[백준/C++][연속합 2(13398번)]

문제

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

13398번: 연속합 2

문제 해결

기존의 연속합 문제에서 변형을 하였다.

기존의 연속합 문제 + 제거할 경우를 생각 했다.

제거 dp를 따로 만들어서 저장했고 dp의 값은 전 값을 제거한 값,그냥 전의 dp값을 받는 경우 2가지를 생각해서 두 값의 max값을 넣어 주었다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    long long N,ary[100002],dp[100002][2] = {0,};
    long long Max;
    cin >> N;
    for(int i = 1;i<=N;i++){
        cin >> ary[i];
    }
    dp[1][0] = ary[1]; dp[1][1] = ary[1]; Max = ary[1];
    for(int i = 2;i<=N;i++){
        if(ary[i]>=dp[i-1][0]+ary[i]){
            dp[i][0] = ary[i];
            Max = max(dp[i][0],Max);
        }
        else{
            dp[i][0] = dp[i-1][0]+ary[i];
            Max = max(dp[i][0],Max);
        }
        dp[i][1] = max(dp[i-1][1]+ary[i],dp[i-2][0]+ary[i]);
        Max = max(dp[i][1],Max);
    }
    cout << Max;
}