-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy pathSolution.java
More file actions
62 lines (54 loc) · 1.54 KB
/
Solution.java
File metadata and controls
62 lines (54 loc) · 1.54 KB
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
58
59
60
61
62
package MaximumSubarray;
/**
* User: Danyang
* Date: 1/22/2015
* Time: 20:49
*
* 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.
*/
public class Solution {
/**
* O(n) iterative is trivial
* Divide and Conquer Approach
* O(n lgn)
* 1. divide in half
* 2. left max sub
* 3. right max sub
* 4. max sub crossing the middle point
* @param A
* @return
*/
public int maxSubArray(int[] A) {
return maxSubArray(A, 0, A.length);
}
int maxSubArray(int[] A, int s, int e) {
if(s>=e)
return Integer.MIN_VALUE;
if(s==e-1)
return A[s];
int m = (s+e)/2;
int l = maxSubArray(A, s, m);
int r = maxSubArray(A, m, e);
int c = maxCross(A, s, e, m);
return Math.max(Math.max(l, r), c);
}
int maxCross(int[] A, int s, int e, int m) {
int max_l = A[m];
int max_r = A[m];
int acc = A[m];
for(int i=m-1; i>=s; i--) {
acc += A[i];
max_l = Math.max(max_l, acc);
}
acc = A[m];
for(int i=m+1; i<e; i++) {
acc += A[i];
max_r = Math.max(max_r, acc);
}
return max_l+max_r-A[m];
}
}