13398 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

연속합 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

4952

1567

1124

30.527%

문제

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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

 

<풀이>

1. 가장 긴 바이토닉 부분 수열을 응용해서 풀 수 있다.

 

2. a1, a2, a3, a4, ..... , a(N-1), a(N) 이라는 임의의 수열이 있을때

임의의 원소가 a[k] 번째 라고 한다면, 문제의 조건에서 어떤 원소를 제거해도 되고 안해도 된다라는 조건이 있기때문에,  a[1] + .... +a[k-1]  + a[k+1] +a[k+2] .... 를 하면 된다.

 

3. 물론 입력될 원소의 개수가 적다면 하나를 제거하고( 0으로 만들고) 다음 원소부터

계속 비교해보고 N번을 N번 비교하므로 O(N^2)으로 할 수 있다. 하지만 입력 데이터 개수가

10만이라면 10만^2이 되버리기때문 연산횟수가 평균 1초 1억이라고했을때 그 수를 훨씬 뛰어 넘기 때문, 시간초과가 발생한다.

 

4. 

 D [0][i] : 특정 원소를 제거 하지 않은 연속합,

 D [1][i] : 특정 원소를 제거한 연속합 이라고 한다면

 

D[0][i] 와 D[1][i]의 제거될 원소 i를 제외하고 둘이 더한 연속의 합의 합을 구할 수 있다.

 

ex ) D[0][i-1]  ,   i(제거될 원소) ,  D[1][i+1]

 

5. 제거 하지 않고도 가장 큰 값이 나올 수 있기때문

 먼저 제거하지 않은 상태에서 최대값을 구해보고, 그 값과 대소 비교를 통해

 구할 수 있다.

 

6. 두 조건의 연속합을 합치기 위해서 D[1][i]를 역으로 구해야 한다.

왜냐하면,

D[0][1] D[0][2]   .. ... D[0][i] D[0][i+1]..

D[1][1] D[1][2]   .. ... D[1][i] D[1][i+1]..

이 두개를 합치려면  i번째 이전의 값들에는 이미 제거 하지 않은 연속합의 부분이 겹치기

떄문이다. 

 

7. 이 겹치는 부분에서 발생할 수 있는 오류를 피하기위해

---------->(연속합 최대)   (제거 원소 i번째 )    (연속합 최대) <--------------

                D[0][i-1]                                    D[1][i+1]

이처럼 두개를 더하면서 각각이 i를 N번씩 다 순회하며 최대값의 합을 찾으면 된다.

 

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

int arr[100001];
int d[2][100001];
int main(void)
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		cin >> arr[i];
	}

	//d[0][n] = 제거 하지 않은, d[1][n] = 제거 한 경우
	for (int i = 1; i <= N; ++i)
	{
		d[0][i] = arr[i];
		if (i == 1) continue;
		d[0][i] = max(d[0][i - 1] + arr[i], arr[i]);

	}
	for (int i = N; i >= 1; --i)
	{
		d[1][i] = arr[i];
		if (i == N) continue;
		d[1][i] = max(d[1][i + 1] + arr[i], arr[i]);
	}
	int ans = -1001;

	for (int i = 1; i <= N; ++i)
	{
		if (ans < d[0][i]) ans = d[0][i];
	}

	for (int i = 2; i <= N; ++i)
	{
		if (ans < d[0][i - 1] + d[1][i + 1])
			ans = d[0][i - 1] + d[1][i + 1];
	}

	cout << ans << '\n';
	return 0;
}