LC 53 Maximum Subarray(S)

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)

边界判断 如果数组没有值，直接返回0

解体思路 DP

采用DP方法， 假设已经知道n-1 的最大累加值，比较和n加之后，哪个最大， 关于数组起点，是比较如果 当前n值比 n的累计还大，起点重置为n

public int maxSubArray(int[] nums) {
    if(nums.length<1)
        return 0;
    int maxTotal = nums[0];
    int curMax = nums[0];
    for(int i = 1; i < nums.length; i++){
        curMax = Math.max(curMax + nums[i], nums[i]);//n的累计值 和 n比较 确定新起点
        maxTotal = Math.max(maxTotal, curMax);
    }
    return maxTotal;
}