最大子数组证明

最大子数组之和问题是一道经典的面试题.
这里对这个问题的迭代解法做一个证明.

先给出C的伪代码

int max_sub_array(int *arr, int len)
{
	int temp = 0, max = arr[0];
	int i;
	for (i = 0; i < len; i++) {
		temp += arr[i];
		if (temp < 0) {
			temp = 0;
		}
		if (temp > max) {
			max = temp;
		}
	}
	return max;
}

算法的思路是这样的:

所以用$temp$存储$A[p..r]$,只要$A[p..r]$求和是负数的话,那么下一个$A[r+1]$开始,$temp$重新清零开始求和,只要$temp$比和大,就更新这个和.

这个算法的思路证明如下:

对于$A[p..r]$,如果$A[p..r]$求和为负数的话,那么数组$A[p..r+1]$的最大子数组肯定不会是$A[p..r+1]$
因为$A[p..r] + A[r+1] < A[r+1]$的.

对数组的所有元素进行一个划分,对于$A[i]$,如果能够使得 $temp>0$ 且 $temp+A[i]<0$,那么这个元素就是一个划分的边界.
这样就会形成很多个区间.

接下来要证明

1. 最大子数组一定在划分块内
2. 一定存在首元素是划分块的首元素的最大子数组

对于第一个点,假设有一个元素$A[i]$在划分区间$A[p..r]$内,那么$A[p..i-1] > 0$ and $A[i..r] < 0$一定成立,这个可以用反证法.

如果一个最大子数组横跨了这些区域假设这个最大子数组为$A[i..j]$,并且$A[r]$最大子数组中最后一个处于分界的元素.
那么$A[i..r] < 0$一定成立,所以最大子数组不可能有这段部分,因此最大子数组只会处于划分内.

对于第二点,假设$A[i..j]$处于划分$A[p..q]$当中,那么$A[p..i-1]+A[i..j] \ge A[i..j]$一定成立,所以最大子数组
的开始元素也是划分的开始元素.

综合起来就能证明这个算法的正确性.

实际上抽象地理解就是把数组划分成了恰好多加一个元素和就变负数的N个划分,而最大子数组不可能超过这个划分,
因此在计算划分当中的最大值就能得到最大子数组.产生一个新的划分的时候如果碰到负数肯定是独自成立了一个划分,如果碰到正数
就会作为新的划分的开始,所以这个划分的第一个元素会成为最大子数组的第一个元素,然后遍历每次包含一个元素以后的和就能确定最大值,最终获得最大子数组.