[백준13398] 연속합2 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int a[100001], DL[100001] = { 0 }, DR[100001] = { 0 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	DL[1] = a[1];
	for (int i = 2; i <= n; i++) {
		DL[i] = a[i];
		if (DL[i-1] > 0)
			DL[i] += DL[i - 1];
	}
	DR[n] = a[n];
	for (int i = n-1; i >= 1; i--) {
		DR[i] = a[i];
		if (DR[i + 1] > 0)
			DR[i] += DR[i + 1];
	}
	int max = DL[1];
	for (int i = 2; i <= n; i++) {
		if (max < DL[i])
			max = DL[i];
	}
	for (int i = 2; i <= n-1; i++) {
		if (max < DL[i - 1] + DR[i + 1])
			max = DL[i - 1] + DR[i + 1];
	}
	cout << max;
	return 0;
}

연속합 수열에서 수 하나를 제거할 수 있다는 조건 때문에 상당히 까다로웠던 문제다. 한참을 고민하고 코드를 짜보다가 제대로 작동하지 않아서 결국 정답 소스코드를 참고했다. 반례가 많은 문제여서 답안을 몇 번이나 제출하고 나서야 정답을 제출할 수 있었다.

📌아이디어

배열 DL[n]과 DR[n]을 사용하였다. DL[n]은 n번째에서 끝나는 부분합 배열의 합, DR[n]은 n은 n번째에서 시작하는 배열의 합이다.

DL[n-1]+DR[n+1]을 구하면 n번째 수를 제외한 부분합 수열의 합을 구할 수 있다. 이 중 최댓값을 찾아주면 문제의 정답이 된다.

다음의 코드 대신

for (int i = 2; i <= n-1; i++) {
		if (max < DL[i - 1] + DR[i + 1])
			max = DL[i - 1] + DR[i + 1];
	}

아래의 코드를 사용할 수도 있다.

for (int i = 2; i <= n; i++) {
		if (max < DL[i] + DR[i] - a[i])
			max = DL[i] + DR[i] - a[i];
	}