首页 > 代码库 > leetcode--Maximum Subarray
leetcode--Maximum Subarray
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
.
click to show more practice.
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.
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | public class Solution { /** * This program is an implementation of divide-and-conquer method * @param A --an array of integer * @return the maximum sum of a subarray * @author Averill Zheng * @version 2014-06-04 * @since JDK 1.7 */ public int maxSubArray( int [] A) { return maxSubArrayHelper(A, 0 , A.length); } /** * The function is used to find the maximum sum of a contiguous subarray between index i (inclusive) and j * (exclusive). * @param A --an integer array. * @param i --start index which is included. * @param j --end index which is exclusive. * @return int --maximum sum of a contiguous subarray. */ private int maxSubArrayHelper( int [] A, int i, int j){ int max = Integer.MIN_VALUE; if (j > i){ if (j == i + 1 ) max = A[i]; else { int mid = i + (j - i) / 2 ; int leftMax = maxSubArrayHelper(A, i, mid); int rightMax = maxSubArrayHelper(A,mid, j); int crossMax = crossMax(A, i, j, mid); max = Math.max(Math.max(leftMax, crossMax), rightMax); } } return max; } private int crossMax( int [] A, int i, int j, int mid){ //[i,mid) is the first half and [mid, j) is the second half //both of them contains at least one element //left max int leftMax = A[mid - 1 ]; int leftSum = A[mid - 1 ]; for ( int k = mid - 2 ; k > i - 1 ; --k){ leftSum += A[k]; leftMax = (leftMax < leftSum) ? leftSum : leftMax; } //right max int rightMax = A[mid]; int rightSum = A[mid]; for ( int k = mid + 1 ; k < j; ++k){ rightSum += A[k]; rightMax = (rightMax < rightSum) ? rightSum : rightMax; } return leftMax + rightMax; } } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。