연속합 2 13398

문제

접근 방법

연속합에 후속 문제이다. 차이점은 수를 1개 제거할 수 있다는 점이다.

연속 합의 경우 현재 시점에서 가장 큰 값은 값을 누적해 가는 것인지 아니면 현재 값으로 새로 시작하는지로 나뉠 것이다. (음수일 경우 버리는 것이 낫다)

수를 1개 제거할 수 있다면 1칸을 뛰어넘어서 누적된 값을 사용할 수 있는 것이다. 하지만 이미 1개를 제거한 경우에는 뛰어넘을 수 없기에 바로 이전의 누적된 값을 사용해야 한다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
vector<vector<int>> dp;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, num, ret;
    cin >> n;
    v = vector<int>(n);
    dp = vector<vector<int>>(2, vector<int>(n));
    cin >> v[0];
    dp[0][0] = v[0];
    ret = dp[0][0];
    for (int i = 1; i < n; ++i)
    {
        cin >> v[i];
        dp[0][i] = max(v[i], v[i] + dp[0][i - 1]);
        if (i >= 1)
        {
            dp[1][i] = dp[1][i - 1];
            if (i > 1)
                dp[1][i] = max(dp[1][i], dp[0][i - 2]);
            dp[1][i] += v[i];
        }
        ret = max(max(dp[0][i], dp[1][i]), ret);
    }
    cout << ret;
    return 0;
}

풀이

1칸을 버린 상태를 따로 저장하면 된다.