[c++] 백준 13398 연속합 2

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

13398번: 연속합 2

#include<bits/stdc++.h>
using namespace std;
#define INF 987654321
/*
dp[i][0] : 아직 숫자 하나 제거하기를 사용하지 않은 경우
dp[i][1] : 숫자 하나 제거하기를 사용한 경우
*/
int dp[100100][2];
//입력 받을 배열
int arr[100100];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    for(int i=0; i<n; i++)
        cin>>arr[i];
    //dp 초기값 설정
    dp[0][0] = dp[0][1] = arr[0];
    for(int i=1; i<n; i++){
        dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]);
        /*
        아직 숫자 제거하기를 사용하지 않았을때
          1.합을 누적시킨것
          2.합을 누적시키지 않고 arr에서 새로운 숫자로 갱신한것
          
          1,2중 최대를 저장
        */
        dp[i][1] = max(dp[i-1][0], max(dp[i-1][1] + arr[i], arr[i]));
        /*
        숫자 제거하기를 사용한 경우
          1.합을 누적시킨것
          2.합을 누적시키지 않고 arr에서 새로운 숫자로 갱신한것
          3.숫자 제거하기를 사용하여 갱신한것
          
          1,2,3중 최대를 저장
        */
    }
    //누적합이 음수일수도 있으므로 최소 음수값으로 초기값 설정
    int ans=-INF;
    //계산 해준 값중 최대값 찾기
    for(int i=0; i<n; i++)
        ans = max(ans,max(dp[i][0], dp[i][1]));
    cout << ans;
    return 0;
}