53 LeetCode :: Maximum Subarray 详细分析

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array  [?2,1,?3,4,?1,2,1,?5,4] , 
the contiguous subarray  [4,?1,2,1]  has the largest sum =  .

这道题，如果看过Mark Allen Weiss写的数据结构与算法分析一书，可以发现是第二章为了介绍算法的魅力，逐步从三次方的时间复杂度一直优化到线性时间复杂度的一个例子。有一点小区别，就是书中给的例子简化了，如果全为负数，则认为最大子序列和为0，所以有一点点出入，不过基本思路是完全一样的。

现在对线性时间解法做一下解释，属于一种DP问题。已知了前k个元素的最大子序列和为maxSub（已经被记录下来了），以及一个临时和sum，如果添加了第k+1这个元素，由于是连续子序列这个限制，所以如果k+1这个元素之前的和是小于0的，那么对于增大k+1这个元素从而去组成最大子序列是没有贡献的，所以可以把sum 置0。举个例子，-1， -2 ，4， -5， 7这里假定7为第k+1个元素，那么很明显可以看出，之前的sum = -5 + 4 =-1，那么这样对于7来说只会减少它，所以直接置sum = 0， 0 + 7才能得到正确的答案。再拓展这个数组， -1， -2， 4， -5， 7， 1 这里1之前的sum = 7 > 0，对于后面的1来组成最大子序列是有贡献的，所以sum = 7 + 1 =8。再注意一点，只要sum不减到负数，中间出现小于0的元素是没关系的，sum仍然可以继续累加。

class Solution {
public:
	int maxSubArray(int A[], int n) {
		int sum = A[0] , maxSum = A[0];
		for(int i = 1; i < n; i++){
			if(sum < 0) sum = 0;   //先判断之前的sum能否被这次利用（小于0则抛弃）
			sum += A[i];
			maxSum = max(maxSum, sum); 
		}
		return maxSum;
	}
};

还有一种分治的解法，时间复杂度是NlogN ，下次再补充一下，这个解法的思路非常清晰，比上一种好理解的多了。