[BOJ10211] Maximum SubArray

[BOJ10211] Maximum SubArray

문제 링크

문제설명

• 유명한 문제인 최대부분배열을 구하는 문제이다.

코드리뷰

• 이전 포스팅 분할정복1을 보면 자세히 설명을 써놓았다.
• 다이나믹 프로그래밍이 아닌 분할정복을 이용하여 푼 코드이다.

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

int arr[1005];
int N;

int MaxCrossingSubArr(int low, int mid, int high) {
	int leftsum = -1000000;
	int rightsum = -1000000;
	int sum = 0;
	for (int i = mid; i >= 0; i--) {
		sum += arr[i];
		if (sum > leftsum) leftsum = sum;
	}
	sum = 0;
	for (int i = mid + 1; i <= high; i++) {
		sum += arr[i];
		if (sum > rightsum) rightsum = sum;
	}
	return leftsum + rightsum;
}
int MaxSubArray(int low, int high) {
	if (low == high) return arr[low];
	int mid = (low + high) / 2;
	int lresult = MaxSubArray(low, mid);
	int rresult = MaxSubArray(mid + 1, high);
	int cresult = MaxCrossingSubArr(low, mid, high);
	return max(lresult, max(rresult, cresult));
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> arr[i];
		}
		int result = MaxSubArray(0, N-1);
		cout << result << '\n';
	}
	return 0;
}

---