最大连续子数组

 给定一个数组A[0,...,n-1], 求A的连续子数组，使得该子数组的和最大

例如：

数组：1，-2，3，10，-4，7，2，-5

最大子数组：3，10，-4，7，2 之和为18

暴力法

int MaxSubArray(int *A, int n)
{
	int maxSum = a[0];
	int currsum;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			currsum = 0;
			for (int k = i; k <= j; k++)
			{
				currsum += A[k];
			}
			if (currsum > maxSum)
				maxSum = currsum;
		}
	}
	return maxSum;
}
           

 分治法

1.  将数组从中间分开，那么最大子数组要么完全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。
2. 完全在左数组、右数组递归解决。
3. 跨立在分界点上：实际上是左数组的最大后缀和右数组的最大前缀的和。因此，从分界点向前扫，向后扫即可。

double MaxAddSub(double *a, int from, int to)
	{
		if (to == from)
			return a[from];
		int middle = (from + to) / 2;
		double m1 = MaxAddSub(a, from, middle);
		double m2 = MaxAddSub(a, (middle + 1, to);

		int i, left = a[middle], now1 = a[middle];
		for (i = middle - 1; i >= from; i--)
		{
			now1 += a[i];
			left = max(now, left);
		}
		int right = a[middle + 1], now2 = a[middle + 1];
		for (i = middle + 2; i <= to; i++)
		{
			now2 += a[i];
			right = max(now, right);
		}
		double m3 = left + right;
		return max(m1, m2, m3);
	}
           

分析法（逻辑推理的算法应用）

1. 前缀和p[i] = a[0]+a[1]+…+a[i]

2.  s[i,j] = p[j] – p[i-1](定义p[-1]=0)

算法过程

1. 求i前缀p[i];

   遍历i：0<=i<=n-1

   p[i] = p[i-1]+A[i]

2. 计算p[i] - p[j]

   遍历i：0<= i <=n-1，求最小值m

   m的初值取0（p[-1]=0）,然后遍历p[0…i-1]，更新m

   p[i] – m即为以a[i]结尾的数组中最大的子数组

3. 在第2步中，可以顺手记录p[i] – m的最大值

int result = a[0], sum = a[0];
	for (int i = 1; i < 8; i++)
	{
		if (sum > 0)
			sum += a[i];
		else
			sum = a[i];
		if (sum > result)
			result = sum;
	}