백준 13398 - 연속합 2

문제

 

www.acmicpc.net/problem/13398

13398번: 연속합 2

 

 

풀이

 

다음과 같은 점화식을 만든다.

1. dp[i][0] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 중간에 삭제를 진행하지 않음

2. dp[i][1] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 이전에 삭제를 진행했다 or 현재 값을 삭제한다.

 

n개의 수열 중에서 dp[n][0]와 dp[n][1] 까지 모두 구했을 때, 그 중에서 최대값을 찾으면 된다.

 

1번을 구하기 위한 점화식은 다음과 같다. 

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

만약 dp[i-1][0]가 음수면, 현재 수열의 값만 선택하는게 연속합의 최대값이 된다. 반대로 dp[i-1][0]가 양수면 헌재 수열의 값도 더해야 연속합이 최대가 된다.

 

 

2번을 구하기 위한 점화식은 다음과 같다.

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

만약 현재 값을 지우면 dp[i-1][0]의 값을 그대로 가져올 것이고, 이전에 삭제를 진행했으면 현재 값은 반드시 포함해야 하므로 dp[i-1][1] + a[i]가 된다.

 

코드

 

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[100000][2]; // 0 : 삭제 x, 1: 삭제 O
int arr[100000];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    int n;
    cin >> n;
 
    for (int i=0; i<n; i++)
        cin >> arr[i];
 
    dp[0][0] = arr[0];
    result = arr[0];
    for (int i=1; i<n; i++) 
    {
        dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]);
        dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]);
        result = max(result, max(dp[i][0], dp[i][1]));
    }
 
    cout << result;
 
    return 0;
}