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

➡️ 출력

첫째 줄에 답을 출력한다.

💻 코드 (C++)

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

int A[100001];
int L[100001];
int R[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	for(int i = 0; i < n; i++) {
		cin >> A[i];
	}
	
	int ans = A[0];
	
	// L[i] 구하기
	L[0] = A[0];
	for(int i = 1; i < n; i++) {
		L[i] = max(A[i], L[i - 1] + A[i]);
		ans = max(ans, L[i]);
	}
	
	// R[i] 구하기
	R[n - 1] = A[n - 1];
	for(int i = n-2; i >= 0; i--) {
		R[i] = max(A[i], R[i + 1] + A[i]);
		ans = max(ans, R[i]);
	}
	
	// 최댓값 구하기
	for(int i = 1; i < n - 1; i++) {
		int tmp = L[i - 1] + R[i + 1];
		ans = max(ans, tmp);
	}
	
	cout << ans;
	return 0;
}