최대 부분 배열 문제 (Maximum subarray problem) 분할 정복으로 풀기

(출처: Introduction to algorithms)

 

'최대 부분 배열 문제' 유명한 문제죠. 비지 않고 연속된 배열의 부분 배열중 가장 큰 합을 가지는 것(=최대 부분 배열)을 찾는 문제입니다.

여러 해법이 있는데 이 게시물에서는 분할 정복으로 풀어보겠습니다.

이 문제를 분할 정복으로 풀면 \(O(n\log n)\)의 시간복잡도를 갖습니다.

 

부분 배열 A[low..high]의 최대 부분 배열 중 하나를 찾는다고 생각해봅시다. 분할정복에서는 부분 배열을 가능한 같은 크기의 두 부분 배열로 나누는게 좋기 때문에 부분 수열의 중간값(mid)을 찾아 두 부분수열 A[low..mid]와 A[mid+1..high]로 나눠봅니다.

이렇게 나눴을 때 부분 배열은 다음 중 하나에 포함됩니다

• 부분 배열 둘 중 하나에 완전히 포함된다
  • A[low..mid]
  • A[mid+1..high]
• 중간값에 걸쳐있다 (low <= i <= mid < j <= high)

두 부분배열 중 하나에 완전히 포함되어 있는 경우, 재귀적으로 찾을 수 있습니다. 이때 base case는 원소가 하나가 될 때입니다.

중간값에 걸쳐있는 경우, mid부터 시작해서 low쪽으로 가면서 최대 부분 배열을 찾고, mid+1부터 시작해 high쪽으로 가면서 최대 부분 배열을 찾아 두 부분 배열을 합쳐서 구할 수 있습니다.

 

 

const int INF = 987654321;

// arr[low..high]의 부분 배열이 중간값에 걸쳐 있는 경우
int find_max_crossing_subarray(const vector<int>& arr, int low, int mid, int high) {
	int left_sum = -INF;
	int right_sum = -INF;

	int sum = 0;
	for (int i = mid; i >= low; --i) {
		sum += arr[i];
		left_sum = max(left_sum, sum);
	}

	sum = 0;
	for (int j = mid + 1; j <= high; ++j) {
		sum += arr[j];
		right_sum = max(right_sum, sum);
	}

	return left_sum + right_sum;
}

// 분할정복
// arr[low..high]의 최대 부분 배열의 합을 구함
int find_max_subarray(const vector<int>& arr, int low, int high) {
	if (high == low)
		return arr[high];

	int mid = (low + high) / 2;
	int left_sum = find_max_subarray(arr, low, mid);
	int right_sum = find_max_subarray(arr, mid + 1, high);
	int cross_sum = find_max_crossing_subarray(arr, low, mid, high);

	return max({left_sum, right_sum, cross_sum});
}

C++로 구현한 코드입니다. 최대 부분 배열의 인덱스까지 구하고 싶은 경우 조금만 수정해주면 됩니다.