题目
- 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.
方法
寻找和最大的子数组, 时间 O(n).
- public int maxSubArray(int[] A) {
- if (A == null) {
- return 0;
- }
- int len = A.length;
- int max = A[0];
- int cur = 0;
- for (int i = 0; i < len; i++) {
- cur += A[i];
- if (max < cur) {
- max = cur;
- }
- if (cur < 0) {
- cur = 0;
- }
- }
- return max;
- }
来源: http://www.bubuko.com/infodetail-3016683.html