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
.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
A:----------CLRS 上的 divide and conquer 算法
public class Solution { public int maxSubArray(int[] A) { // same with the buy&sell stock problem return maxSubArray(A,0,A.length-1); } private int maxSubArray(int[] A, int low, int high) { if(low==high){ return A[low]; }else{ // low < high int mid = (low+high)/2; int maxLeft = maxSubArray(A,low,mid); int maxRight = maxSubArray(A,mid+1,high); int maxCross = maxCrossArray(A,low,mid,high); return Math.max(maxRight, Math.max(maxLeft, maxCross)); } } private int maxCrossArray(int[] A, int low, int mid, int high) { // left part int sum = 0 ,maxLeftSum = A[mid]; for(int i =mid;i>=low;i--){ sum += A[i]; if(sum>maxLeftSum){ maxLeftSum = sum; } } // right part sum = 0; int maxRightSum = A[mid+1]; for(int i = mid+1;i<=high;i++){ sum+=A[i]; if(sum>maxRightSum){ maxRightSum = sum; } } return maxLeftSum + maxRightSum; } }
----------------------Kadane's algorithm ----------- O(n) ---
-------IDEA: keep two values, maxSoFar, maxEndingHere------------从前面开始,逐个加入数组的值。--------
public class Solution { public int maxSubArray(int[] A) { int maxSoFar = Integer.MIN_VALUE/2; int maxEndHere = Integer.MIN_VALUE/2; for (int i = 0; i < A.length; i++) { if (maxEndHere <= 0) { maxEndHere = A[i]; } else { maxEndHere += A[i]; } // update max_so_far if (maxEndHere > maxSoFar) { maxSoFar = maxEndHere; } } return maxSoFar; } }-------------------第二遍------------------就是用空间换时间-----------
public class Solution { public int maxSubArray(int[] A) { // space to time int n = A.length; if(n==0) return 0; int maxSum[] = new int[n]; // max sum till current position maxSum[0] = A[0]; for(int i =1;i<n;i++){ maxSum[i] = Math.max(A[i], A[i]+maxSum[i-1]); } // find maxsum value in maxSum int result = maxSum[0]; for(int i =1;i<n;i++){ if( result < maxSum[i] ) result = maxSum[i]; } return result; } }
-----------------3 rd Pass -----------不用数组空间, 只需要一个变量,记录max sum value ending here 即可------
对比上面的实现, 是 利用 语句
A[i] + Math.max(0,maxEndHere);中, A[i] 在外边, 这样,保证了后面的,不会溢出。就是说,避免了像上面那样, Integer,MIN_VALUE + 负数 的情况出现
public class Solution { public int maxSubArray(int[] A) { // if(A.length==0) // return 0; int totalMax =Integer.MIN_VALUE,maxEndHere=0; for(int i =0;i<A.length;i++){ maxEndHere =A[i] + Math.max(0,maxEndHere); totalMax = Math.max(totalMax, maxEndHere); } return totalMax; } }
注意: 这里, 其实A.length==0的情况, LC的test case 中估计是没有出现。 或者说,没有定义。 因此,当A为空的时候, 我们这里返回最小值是可以的。
---------------4th pass------------------------
思路就是: 把所有的全加起来,这样,和就是现在这个减前一个最小的即可。
public class Solution { public int maxSubArray(int[] A) { if(A==null || A.length == 0) return 0; for(int i =1;i<A.length;i++) A[i] += A[i-1]; int minLeft = 0,result = A[0]; for(int i =0; i<A.length;i++){ result = Math.max(result, A[i] - minLeft); if(A[i]<minLeft) minLeft = A[i]; } return result; } }
Mistakes:
1: minLeft刚开始没有想象成是-1的位置。 转而设置成 Integer.MIN_VALUE了。这样是不对的
Learned:
No comments:
Post a Comment