연속합 2

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	20353	6150	4550	29.754%

문제

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

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

예제 출력 1

54

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: dj910401, ha_ram, solarmagic
• 문제의 오타를 찾은 사람: jh05013
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 다이나믹 프로그래밍

---

시간 초과 코드 (Brute Force)

N의 범위가 100,000로 모든 경우의 수를 확인하면 시간 복잡도가 O(N^2)이 넘어간다 (대략 O(N^3)?)

#include <iostream>
using namespace std;
int _Arr[100001], _N, _Res = INT32_MIN;
int _DP[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	for (int i = 1; i <= _N; i++)
		cin >> _Arr[i];
	for (int i = 1; i <= _N; i++) {
		_DP[i] = _DP[i - 1] + _Arr[i];
		_Res = max(_Res, _DP[i]);
	}

	for (int i = 1; i <= _N; i++)
		for (int j = 0; j <= i - 2; j++) {
			_Res = max(_Res, _DP[i] - _DP[j]);
			for (int k = j + 1; k <= i; k++)
				_Res = max(_Res, _DP[i] - _DP[j] - _Arr[k]);	
		}
	cout << _Res;
	return 0;
}

통과된 코드 (DP)

DP[0][i] : i번째 수를 포함하여 연속된 수를 선택했을 때의 최대 합을 계산합니다.
이전 최대 합인 _DP[0][i-1]과 i번째 수인 _Arr[i]를 더한 값과, i번째 수를 단독으로 선택한 값 중 더 큰 값을 선택하여 저장

DP[1][i] : i번째 수를 제거하고 연속된 수를 선택했을 때의 최대 합을 계산합니다.
이전 최대 합인 _DP[0][i-1]과 i번째 수인 _Arr[i]를 더한 값 중 더 큰 값을 선택하여 저장

시간 복잡도는 O(N)

#include <iostream>
using namespace std;
int _Arr[100000], _N, _Res;
int _DP[2][100000];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	for (int i = 0; i < _N; i++)
		cin >> _Arr[i];
	_Res = _DP[0][0] = _Arr[0];
	_DP[1][0] = 0;
	for (int i = 1; i < _N; i++) {
		_DP[0][i] = max(_DP[0][i - 1] + _Arr[i], _Arr[i]);
		_DP[1][i] = max(_DP[0][i - 1], _DP[1][i - 1] + _Arr[i]);
		_Res = max(_Res, max(_DP[0][i], _DP[1][i]));
	}
	cout << _Res;
	return 0;
}