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.前缀法。第一个优化是把连续和转变为sum[j] - sum[i]的值。第二个优化是引入前缀，一直记录前i个数里最小的sum[i]，那你每次算i~j和的时候肯定是要减去这个最小前缀才能让差值最大化的。
2.贪婪法。每次如果发现当前的sum变成负数了就立即舍去，下一个数加进来的时候肯定选择不要前面这串累赘的。
1.前缀法实现
class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] sums = new int[nums.length + 1]; sums[0] = 0; for (int i = 0; i < nums.length; i++) { sums[i + 1] = sums[i] + nums[i]; } int minPreSum = sums[0]; int maxSum = Integer.MIN_VALUE; for (int i = 1; i < sums.length; i++) { int crtSum = sums[i] - minPreSum; maxSum = Math.max(maxSum, crtSum); minPreSum = Math.min(minPreSum, sums[i]); } return maxSum; } }
2.贪心法实现
class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxSum = Integer.MIN_VALUE; int localSum = 0; for (int i = 0; i < nums.length; i++) { localSum += nums[i]; maxSum = Math.max(maxSum, localSum); localSum = Math.max(localSum, 0); } return maxSum; } }
leetcode53- Maximum Subarray- easy
原文：http://www.cnblogs.com/jasminemzy/p/7818815.html