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 = 6.

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere+nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

sum[i] = max(nums[i], sum[i-1] + nums[i+1])
result = max(result, sum[i])

显然nums[i]与nums[i]+sum[i-1]孰大孰小，完全取决于sum[i-1]的正负，所以代码也可以这样写：

    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) {
    		return 0;
    	}
    	int max = A[0];
    	int curSum = A[0];
    	for (int i = 1; i < A.length; i++) {
    		if (curSum < 0) {
    			curSum = A[i];
    		} else {
    			curSum += A[i];
    		}
    		if (max < curSum) {
    			max = curSum;
    		}
    	}
    	return max;
    }     

这个算法还是比较经典的，好多算法也用到了这个特性，比如，maxEndingHere或者maxBeginingHere。

LeetCode-Maximum Subarray

原文：http://blog.csdn.net/my_jobs/article/details/47978137