53. Maximum Subarray
Problem: 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 . 3/29/2018 update: 更新maxEndingHere在sum[0, i - 1] 小于0的情况下，如果当前nums[i] > 0,肯定要把之前的都抛弃。maxEndingHere不一定是包含了0 ~ i所有的数。 相当于维护一个当前的极大和，因为是求subarray，所以最大和肯定是极大和的最大值。 2/23/2018 update DP solution: maxEndingHere is the max sum from nums[0] to nums[i] that includes nums[i]. public static int maxSubArray( int [] A ) { int maxSoFar = A [ 0 ], maxEndingHere = A [ 0 ]; for ( int i = 1 ;i < A . length; ++ i){ maxEndingHere = Math . max(maxEndingHere + A [i], A [i]); maxSoFar = Math . max(maxSoFar, maxEndingHere); } return maxSoFar; } 10/10/2017 第二种解法用prefix sum的思路来做。 前i个数的maximum subarray = prefixSum[i] - min(prefixSum[0]....prefixSum[i-1])。 在遍历数组的时候需要记录下minSum, s...