分治法解决数据最大子段和的问题

有这么一段数据：int nums[] = {-8, 11, -4, 13, -9, -10};要求求出其中最大子段和，即其中某一连续的几个数据之和最大值，比如这段数据，显然是11+(-4)+13=20为答案。

使用C程序实现的算法，属于分治法。思路是：从中间划开，下标0~5，中间位置(0+5)/2（整除） = 2，那么取0~2，3~5两段下标，递归求最大子段和，用这两个最大字段和，同从2下标开始往左累加，往右累加的最大值，三者比较，取最大值即是最终解。

分治法解决这个问题的根本在于利用递归，实现了从数组的所有下标为标准往两边累加找最大累加值。找出所有情况下的最大累加值就是答案。

 

#include <stdio.h>

int maxSubValues(int nums[], int minIndex, int maxIndex) {
	int sum = 0;
	int allMax = 0;
	int leftMax = 0;
	int rightMax = 0;
	int middleIndex = (minIndex + maxIndex) / 2;
	int i;
	if (minIndex == maxIndex) { // 数组就一个元素了
		if (nums[minIndex] < 0) { // 最大子段有个规定，如果数据都是负数，最大子段值为0
			return 0;
		} else {
			return nums[minIndex];
		}
	}
	leftMax = maxSubValues(nums, minIndex, middleIndex);
	rightMax = maxSubValues(nums, middleIndex+1, maxIndex);
	for (i=middleIndex; i>=0; i--) { // 从中点往左累加最大值
		sum += nums[i];
		if (allMax < sum) {
			allMax = sum;
		}
	}
	sum = allMax; // 保留最大值
	for (i=middleIndex+1; i <= maxIndex; i++) {
		sum += nums[i]; // 往左累加最大值继续累加，找到左右累加最大值
		if (allMax < sum) {
			allMax = sum;
		}
	}
	// 比较左侧最大子段和右侧最大子段还有中间往两边累加的最大值看看谁更大
	if (allMax < leftMax) {
		allMax = leftMax;
	} else if (allMax < rightMax) {
		allMax = rightMax;
	}
	return allMax;
}

int main(int argc, char **argv) {
	int nums[] = {-8, 11, -4, 13, -9, -10};
	printf("max sub:%d\n", maxSubValues(nums, 0, sizeof nums / sizeof(int) - 1));
	return 0;
}