题目原型:
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
.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
基本思路:
令数组为A,从前往后累加得tmp,sum为最大的累加和。
1、如果A[i]>A[i]+tmp,表示,加了还不如不加,那么初始化tmp,令tmp=A[i]。若tmp>sum,则更新sum 。
2、否则,累加tmp,同时注意更新sum。
public int maxSubArray(int[] A) { if(A.length==0||A==null) return 0; int sum = A[0]; int tmp = A[0]; for(int i = 1;i<A.length;i++) { if(A[i]>tmp+A[i]) { tmp = A[i]; } else { tmp+=A[i]; } if(sum<tmp) sum = tmp; } return sum; }
原文:http://blog.csdn.net/cow__sky/article/details/19963235