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

문제링크 : https://www.acmicpc.net/problem/13398

13398번: 연속합 2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[100001];
int dp[100001][2]; //제거하지 않은 경우와 제거한 경우

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, result = 0;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    dp[0][0] = arr[0];
    dp[0][1] = arr[0];
    result = arr[0];

    for(int i=1; i<N; i++)
    {
        dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]);  //제거 x
        dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]); //제거 o
        result = max({result, dp[i][0], dp[i][1]});
    }

    cout << result;

    return 0;

}

dp 배열이 제거한 경우와 제거하지 않은 경우 이렇게 2가지가 필요하다.

 

제거하지 않았을 경우에는 단순히 여태까지 더해온 값과, 현재 값중에 비교하여 더 큰 값을 기준으로 계속해서 더해간다.

제거하였을 경우에는 제거한 경우의 값 + 현재 값과 여태까지 더해온 값을 비교하여 앞으로 새로 제거할지, 기존에 제거한 값 기준으로 계속 더해온 값을 유지할지 정한다.

 

dp[i][1] = max(dp[i-1][0], dp[i-1][1]+ arr[i]) 에서

처음에 i = 1이므로 dp[0][0]을 고를지, dp[0][1] + arr[i]를 고를지 선택한다.

여기서 각 값은 10, 과 10 + (-4)인데 앞을 고름으로써 뒤의 -4를 제거한 것을 알 수 있다.

제거하지 않아도 되기에, 뒤에 값이 더 크다면 뒤에 값으로 계속 진행해도 무방하다.

 

그러면 앞으로 -4를 제거한채로 더해주는 값과, 기존에 그냥 계속 더해온 값을 비교한다.

그러다가 그냥 게속 더해온 값이 커지는 경우가 생기면 새롭게 제거할 값이 생긴 것이다.

예제의 경우 -35의 경우다.

 

이후 이를 반복한다.