[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 연속합 2 (13398)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 연속합 2 (13398)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 연속합 2 (13398)

 

---

 

13398번: 연속합 2

[ 문제 ]

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

[ 입력 ]

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

[ 출력 ]

첫째 줄에 답을 출력한다.

 

---

[ 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

// A[0] 제외 경우, A[1] 제외 경우 .. 하나씩 다 구하는 것은 너무 오랜 시간이 걸림

// DL[i] = i번째 수에서 끝나는 최대 연속합 (i번째 왼쪽)
// DR[i] = i번째 수에서 시작하는 최대 연속합 (i번재 오른쪽)
// DL[i] + DR[i] = i번째 수를 제거했을 때, 최대 연속합

int DL[100001];
int DR[100001];

int main() {
	int N; // 정수 n
	cin >> N;

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

	// DL구하기 (0<=i<=N-1)
	for (int i = 0; i < N; i++)
	{
		DL[i] = arr[i];
		if (i==0)
		{
			continue;
		}
		if (DL[i] < DL[i - 1] + arr[i])
		{
			DL[i] = DL[i - 1] + arr[i];
		}
	}

	// DR 구하기 (N-1>=i>=0)
	for (int i = N-1; i >= 0; i--)
	{
		DR[i] = arr[i];
		if (i==N-1)
		{
			continue;
		}
		if (DR[i] < DR[i + 1] + arr[i])
		{
			DR[i] = DR[i + 1] + arr[i];
		}
	}

	// 아무 수도 제거하지 않았을 경우, 연속합 최대값
	int result = DL[0];
    // result = 0; for문 i=0부터 돌리기는 안되는 이유 : DL[0]의 값이 음수일수도 있기 때문
	// result = 0이라고 해놓으면, DL[0]의 값은 들어가지 못함.
	// DL[0]을 제외하고 다른 값들도 모두 음수라면 이 구문은 적용되지 않음
	// DL[0]을 기준으로 상대적으로 생각해야함.
	for (int i = 1; i < N; i++)
	{
		if (result < DL[i])
		{
			result = DL[i];
		}
	}

	// arr[i]가 제거되었을 경우, 연속합 최대값.
	// result보다 값이 클 경우, 최종 결과

// 0번지와 n-1번지를 제거하는 것은 어디 코드에 포함되어있는가?
// 0번째를 제외하는 것이 더 이득이었다면, 이미 그를 제외하고 계산되었을 것임

	for (int i = 1; i < N-1; i++)
	{
		if (result < DL[i - 1] + DR[i + 1])
		{
			result = DL[i - 1] + DR[i + 1];
		}
	}

	cout << result;
	return 0;
}