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

문제

https://www.acmicpc.net/problem/13398
n개의 정수로 이루어진 수열이 있다.
이 중 연속된 몇 개(최소 1개)를 선택해서 그 합이 최대가 되도록 한다.
단, 선택된 수열 중 하나의 수를 뺄 수 있다.

---

풀이

다만 이 문제에서는 1개를 뺄지 말지 선택해야하기 때문에 배열이 2개 필요하다.

• dp[i][0] = 1 ~ i 까지 수열 중 하나도 빼지 않은 부분합
  이전까지에 나를 껴서 가기, 나부터 시작하기 중 더 큰 값을 택한다.

dp[i][0] = max(dp[i-1][0]+a[i], a[i])

• dp[i][1] = 1 ~ i 까지 수열 중 하나 뺀 부분합

하나 뺀 부분합에 나를 낄지, 하나도 안뺀 부분합에 나를 뺄지 선택하면 되겠다.

dp[i][1] = max(dp[i-1][1]+a[i], dp[i-1][0])

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[100001], m, dp[100001][2], ret;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

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