[DP] 13398. 연속합 2

 

13398번: 연속합 2

 

연속합 2 문제는 연속합 1 문제에서 숫자를 하나 뺀 경우까지 조사한다는 점에서 차이가 있습니다. 

1912번: 연속합

 

 

예를들어 수열 A가 다음과 같을 때,

10 -4 3 1 5 6 -35 12 21 -1

 

연속합 1 문제에서는 수열에서 몇개의 수를 선택해서 더하였을 때, 가장 큰 값을 문제라면

연속합 2 문제에서는 수열에서 몇개의 수를 선택하되 하나의 수를 제거할 수 있는 경우까지 계산해야 합니다.

 

필자는 길이 N의 수열에 대하여

D[0][N] = 길이 N까지의 수열 중 연속합 1에서 구한 수열에서 몇개의 수를 선택하여 제거하지 않았을 때 최댓값 

D[1][N] =  길이 N까지의 수열 중 0 ~ N까지의 인덱스 중 하나의 수를 제거했을 때 최댓값

을 계산하였습니다.

 

D[0][N] - 연속합 1 문제와 동일

1) D[0][1] = v[0] 길이가 1인 수열 중 몇개의 수를 선택했을 때 합의 최댓값 

 

2) (0 ~ N-1 까지의 최대 연속합 값 + 수열의 N번째 값) < (수열의 N번째 값) 인 경우 

: 0 ~ N-1까지의 최대 연속합 값 + 수열의 N번째 값을 더한 값이 수열의 N번째 값보다 작다면 0~N-1까지의 최대 연속합 값은 잊어버리고, 새로 연속합 수열을 시작해야겠죠. 따라서 D[N][0]은 연속합 수열의 시작이 되어야 하므로 D[0][N] 값을 수열의 N번째 값으로 초기화 해주어야 합니다.

 

3) (0 ~ N-1 까지의 최대 연속합 값 + 수열의 N번째 값) >= (수열의 N번째 값) 인 경우

: D[0][N]은 0~ N-1 까지의 최대 연속합 값에서 수열의 N번째 값을 더해준 값이 됩니다. 연속합 수열을 새로 시작하지 않고 계속해서 더해준다는 의미

 

4) 도출한 점화식 D[0][N] = max(D[0][N-1] + v[N] , v[N])

 

1번째 점화식 구현 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int n;

vector<int> v(100001,0);
int d[3][100001];
int ans = -1001;
int main()
{
    FASTio;
    cin >> n;
    
    for(int i=0;i<n;i++)
    {
        cin >> v[i];
    }

    d[0][0] = v[0];

    for(int i=1;i<n;i++)
    {       
        d[0][i] = max(v[i]+d[0][i-1],v[i]);
    }

 

지금까지 제거하지 않은 경우에 대해 길이 N까지의 수열의 연속합의 최댓값을 D[0][N]에 구하였습니다.

 

이제 D[1][N] =  길이 N까지의 수열에서 0 ~ N까지의 인덱스 중 하나의 수를 제거했을 때 수열 연속값의 최댓값을 구해봅시다.

 

 

 

 

1) D[1][1] = 인덱스 1~1까지 1개의 수를 제거했을 때 최댓값 ( 1번째 인덱스를 지우게 되어 0이라고 생각했는데 0을 대입하고 채점해보니 틀렸습니다. 문제의 조건에는 이 조건이 제시되어 있지 않지만, 아마도 길이가 2이상일 때만 제거할 수 있는 것 같습니다 ) 

 

2) D[1][2] = 1~2까지 인덱스 중 1개 제거시 연속 수열의 최댓값 = 10 ( 2번째 인덱스 값을 지워서 10 )

 

3) D[1][3] = 1~3까지 인덱스 중 1개 제거시 연속 수열의 최댓값  = 13 ( 2번째 인덱스 값을 지워 13 )

 

...

 

7) D[1][7] = 1~7까지 인덱스 중 1개 제거시 연속 수열의 최댓값 = 21 ( 7번째 인덱스 값을 지웠을 경우 )

 

 N번째 인덱스 값을 제거한 경우의 연속 수열의 최댓값은
0~N-1 중 아무것도 제거하지 않았을 경우 연속 수열의 최댓값과 같습니다. 따라서 D[0][N-1]라고 볼 수 있습니다.

 

따라서 점화식은 D[1][N] = max(v[N] + D[1][N-1], D[0][N-1])으로 유도할 수 있습니다.

2번째 점화식 구현 코드 

d[1][0] = v[0];

for(int i=1;i<n;i++)
{
    d[1][i] = max(d[1][i-1] + v[i], d[0][i-1]); 
}

 

 

마지막으로 첫번째 점화식에서 1~N까지의 D[0][N]의 최댓값과, 두번째 점화식에서 1~N까지의 D[1][N]의 최댓값을 구하고, 이 두 최댓값 을 비교하여 더 큰 값이 정답이 되겠습니다.

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int n;

vector<int> v(100001,0);
int d[3][100001];
int ans = -1001;
int main()
{
    FASTio;
    cin >> n;
    
    for(int i=0;i<n;i++)
    {
        cin >> v[i];
    }

    d[0][0] = v[0];
    for(int i=1;i<n;i++)
    {       
        d[0][i] = max(v[i]+d[0][i-1],v[i]);
    }

    d[1][0] = v[0];
    for(int i=1;i<n;i++)
    {
        d[1][i] = max(d[1][i-1] + v[i], d[0][i-1]); 
    }

    for(int i=0;i<2;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans = max(ans,d[i][j]);
        }
    }
    cout << ans;
    return 0;
}