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.
|
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; }} |
leetcode--Maximum Subarray,布布扣,bubuko.com
原文：http://www.cnblogs.com/averillzheng/p/3771905.html