《算法导论》——分治法求解最大子数组

《算法导论》——分治法求解最大子数组

最大字数组问题即对某一数组A，其元素有正有负，找到一个子数组，其元素是连续的且其和最大。

#include "iostream"
using namespace std;

struct uin      //创建返回值数据结构
{
	int low;     //最大子数组的左起点
	int high;    //终点
	int sum;	//值
};
uin Find_crossmax(int*a, int left, int right, int mid)//若最大子数组包含中点
{
	uin res;
	int leftsum = INT32_MIN;
	int rightsum = INT32_MIN;
	int sum = 0;
	for (int i = mid; i >= left; i--)
	{
		sum += a[i];
		if (sum > leftsum)
		{
			leftsum = sum;     //左侧连续的最大值
			res.low = i;
		}
	}
	sum = 0;
	for (int i = mid + 1; i <= right; i++)
	{
		sum += a[i];
		if (sum > rightsum)
		{
			rightsum = sum; // 右侧连续的最大值
			res.high = i;
		}
	}
	res.sum = leftsum + rightsum;
	return res;
}
uin Find_maxsubarry(int* a, int left, int right, int mid)
{
	uin result;
	if (left == right)         //递归到最后时返回
	{
		result.low = left;
		result.high = right;
		result.sum = a[left];
		return result;
	}
	uin lsum = Find_maxsubarry(a, left, mid, (left + mid) / 2);
	uin rsum = Find_maxsubarry(a, mid + 1, right, (mid + 1 + right) / 2);
	uin crosssum = Find_crossmax(a, left, right, mid);
	if (lsum.sum >= rsum.sum && lsum.sum >= crosssum.sum)
		return lsum;
	else if (rsum.sum >= lsum.sum && rsum.sum >= crosssum.sum)
		return rsum;
	else if (crosssum.sum >= rsum.sum && crosssum.sum >= lsum.sum)
		return crosssum;

}

void main()
{
	int a[] = { 8, -1, -5, 4, 9, -8, 0, 1 };
	int len = sizeof(a) / sizeof(a[0]);
	uin ptr = Find_maxsubarry(a, 0, len - 1, (0 + len - 1) / 2);
	cout << "最大子数组的左起始为" << ptr.low << " " << "右起始为" << ptr.high << " " << "最大值为：" << ptr.sum << endl;
	system("pause");
}