-
Notifications
You must be signed in to change notification settings - Fork 2
/
MaximumSubarray.java
36 lines (35 loc) · 1.17 KB
/
MaximumSubarray.java
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
public class Solution {
public int maxSubArrayDP(int[] A) {
int prev = A[0];
int result = prev;
for (int i = 1; i < A.length; i++) {
int curr = Math.max(prev+A[i], A[i]);
prev = curr;
result = Math.max(result, curr);
}
return result;
}
public int maxSubArrayDivideConquer(int[] A) {
if (A.length == 1) {
return A[0];
}
int low = 0;
int high = A.length - 1;
int mid = (low + high) / 2;
int left = maxSubArray(Arrays.copyOfRange(A, 0, mid+1));
int right = maxSubArray(Arrays.copyOfRange(A, mid+1, A.length));
int mid_left = Integer.MIN_VALUE;
int mid_right = Integer.MIN_VALUE;
int left_total = 0;
int right_total = 0;
for (int i = mid; i >= 0; i--) {
left_total = left_total + A[i];
mid_left = Math.max(mid_left, left_total);
}
for (int i = mid+1; i < A.length; i++) {
right_total = right_total + A[i];
mid_right = Math.max(mid_right, right_total);
}
return Math.max(left, Math.max(right, mid_left+mid_right));
}
}