[BOJ 26862 // C++] Maxdifficent Group

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26862번 문제인 Maxdifficent Group이다.
문제는 아래 링크를 확인하자.

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

 

배열을 여러 구간으로 나눴을 때, 어떤 인접한 두 구간의 값의 차가 가장 큰 둘을 남겨두고 다른 부분은 아무렇게나 나누어도 있어도 값의 차의 최댓값이 줄어들지는 않음을 관찰하자. 따라서 전체 구간을 나누는 것을 고려할 필요 없이, 인접한 두 구간의 수의 차가 최대가 되게끔 하는 두 구간을 찾는 것으로 문제를 해결할 수 있다.

 

어떤 수를 기준으로 인덱스가 감소하는(왼쪽) 방향으로 연속하는 수의 합 중 최대 및 최솟값이 무엇인지, 오른쪽으로는 어떤지를 구하고, 해당 값을 이용해 두 구간이 인접하고 있을 수 있는 모든 위치에 대하여 그곳에서 두 구간이 인접할 때의 값의 최댓값을 모두 살펴 문제를 해결하자. Kadane's algorithm을 이용해 빠르게 필요한 전처리를 할 수 있다.

 

아래는 제출한 소스코드이다.

//kadane's algorithm
#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll A[100000];
ll mxL[100000], mnL[100000], mxR[100000], mnR[100000];
ll ans = -1000000000000000000LL;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (ll i = 0, val = 0; i < N; i++) {
		val += A[i];
		mxL[i] = val;
		if (val < 0) val = 0;
	}
	for (ll i = 0, val = 0; i < N; i++) {
		val += A[i];
		mnL[i] = val;
		if (val > 0) val = 0;
	}
	for (ll i = N - 1, val = 0; i > -1; i--) {
		val += A[i];
		mxR[i] = val;
		if (val < 0) val = 0;
	}
	for (ll i = N - 1, val = 0; i > -1; i--) {
		val += A[i];
		mnR[i] = val;
		if (val > 0) val = 0;
	}

	for (int i = 0; i + 1 < N; i++) {
		ans = max(ans, mxL[i] - mnR[i + 1]);
		ans = max(ans, mxR[i + 1] - mnL[i]);
	}

	cout << ans;
}