4.1 分治法(最大子數組)

A[low…high]的任何連續子數組A[i…j]所處的位置必然是以下三種情況之一：

1. 完全位于子數組A[low…mid]中， low <=i<=j<=mid.
2. 完全位于子數組A[mid+1…high].mid<i<=j<=high

3. 跨越了中點，low<=i<=mid<j<=high.

   時間複雜度 O(nlgn) + O(n)，其中O(n)為跨越中點的時間。

代碼實作如下

#include <iostream>
#include <limits>

using namespace std;

//函數聲明為指針類型，則函數體内傳回的也應是指針位址，數組會有警告 
int * findMaxSubarray(int A[], int low, int high);
int * findMaxCrossingSubarray(int A[], int low, int mid, int high);

int main()
{
	//指針聲明後需配置設定記憶體 
	int *res = new int[3];
	int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
	res = findMaxSubarray(A, 0, 15);
	while(*res)
	{
		cout << *res << ' ';
		res ++;
	}
	return 0;
}

int * findMaxSubarray(int A[], int low, int high)
{
	int mid;
	//0:左索引，1:右索引，2:所求子數組之和 
	int *tuple  = new int[3];
	int *Ltuple = new int[3];
	int *Rtuple = new int[3];
	int *Ctuple = new int[3];;
	if(low == high)
	{
		tuple[0] = low;
		tuple[1] = high;
		tuple[2] = A[low];
		return tuple;
	}
	else
	{
		mid = (low + high) / 2;
		Ltuple = findMaxSubarray(A, low, mid);
		Rtuple = findMaxSubarray(A, mid + 1, high);
		Ctuple = findMaxCrossingSubarray(A, low, mid, high);
		if((Ltuple[2] >= Rtuple[2]) && (Ltuple[2] >= Ctuple[2]))
			return Ltuple;
		else if((Rtuple[2] >= Ltuple[2]) && (Rtuple[2] >= Ctuple[2]))
			return Rtuple;
		else
			return Ctuple;
	}
}

int * findMaxCrossingSubarray(int A[], int low, int mid, int high)
{
	int *tuple = new int[3];
	int leftSum = INT_MIN;
	int leftIndex;
	int sum = 0;
	for(int i = mid; i >= low; i --)
	{
		sum += A[i];
		if(sum > leftSum)
		{
			leftSum = sum;
			leftIndex = i;
		}
	}
	int rightSum = INT_MIN;
	int rightIndex;
	sum = 0;
	for(int j = mid + 1; j<= high; j ++)
	{
		sum += A[j];
		if(sum > rightSum)
		{
			rightSum = sum;
			rightIndex = j;
		}
	}
	tuple[0] = leftIndex;
	tuple[1] = rightIndex;
	tuple[2] = rightSum + leftSum;
	return tuple;
}
           

輸出結果：

7 10 43