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

출력

첫째 줄에 답을 출력한다.

문제 링크

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

예제 입력 1

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

예제 출력 1

solve

d[i] = i번째 수로 끝나는 가장 큰 연속합
d2[i]는 i번째 수부터 시작하는 연속합
d[1] 부터 이전 수까지의 최대 연속합(d[i - 1] + a[i])과 현재 수열의 원소(a[i])와 비교하여 더 큰 값을 d[i]에 저장한다.
- d[i] = max(d[i-1]+a[i], a[i]) 의 과정을 n까지 반복한다.
d[i]의 최댓값을 초기 결과값에 저장한다.
- 수를 제거하지 않을 수도 있다고 했기 때문에 제거하지 않은 경우 정답을 먼저 구한다.
d2[i]는 뒤(i = n)에서부터 접근하여 i까지의 가장 큰 연속합을 구한다.
- d2[i] = max(d[i + 1] + a[i], a[i]) 의 과정을 i까지 반복
먼저 구해둔 제거하지 않는 경우의 ans와 d[i - 1] + d2[i + 1](i를 제거하는 경우)의 모든 경우와 비교하여 최댓값을 출력

코드 설명

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 100001;
int d[MAX]; // d[i]는 i번째 수로 끝나는 연속합
int d2[MAX]; // d2[i]는 i번째 수부터 시작하는 연속합
int a[MAX]; // 입력 수열
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1, j = 0; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++) // i번째 수로 끝나는 최대 연속합을 구한다.
	{
		d[i] = a[i];
		if (d[i - 1] + a[i] > a[i]) //  i-1까지의 최대 연속합에 현재 수를 더한 것이 현재 수보다 더 큰지 비교
			d[i] = d[i - 1] + a[i];

	}

	for (int i = n; i >= 1; i--) // i번째 수로 시작하여 n으로 끝나는 최대 연속합을 구한다.
	{
		d2[i] = a[i];
		if (i == n)	continue; // i + 1은 접근하면 안되므로
		if (d2[i] < d2[i + 1] + a[i]) // i는 n - 1부터 감소하며 비교
			d2[i] = d2[i + 1] + a[i];

	}

	int ans = d[1];
	for (int i = 1; i <= n; i++)	// 수를 제거하지 않을 수도 있으므로
		ans = max(ans, d2[i]);	// 제거하지 않는 경우 정답을 구해놓는다.

	for (int i = 1; i <= n; i++)
	{
		if (n == 1) continue;  // 최소 한 개의 수를 선택하는 조건이 우선
		ans = max(ans, d[i - 1] + d2[i + 1]);
	}

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

백준 13398번 연속합 2

Baekjoon algorithm