53-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.

【分析】

1.采用动态规划的思想求解

2.假设数组[0,1,.i.,n],其中j到k为最大子数组,则（j-1前的任意值）到j-1都小于0；

【算法实现】

public class Solution {
    public int maxSubArray(int[] nums) {
        int max=Integer.MIN_VALUE;
        int sum=0;
        for(int i=0;i<nums.length;i++) {
            sum+=nums[i];
            if(max<sum)
                max=sum;
            if(sum<0)
                sum=0;
        }
        return max;
    }
}

53-Maximum Subarray

原文：http://www.cnblogs.com/hwu2014/p/4462391.html