-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_53.java
More file actions
81 lines (73 loc) · 2.41 KB
/
Copy pathP_53.java
File metadata and controls
81 lines (73 loc) · 2.41 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package leetcode.easy;
import java.util.Arrays;
public class P_53 {
public int maxSubArrayEPI(int[] nums) {
int minSum = 0, sum = 0, maxSum = 0, max = Integer.MIN_VALUE;
for (int num : nums) {
sum += num;
max = Math.max(max, num);
minSum = Math.min(minSum, sum);
maxSum = Math.max(maxSum, sum - minSum);
}
return max < 0 ? max : maxSum;
}
public int maxSubArrayKadane(int[] nums) {
int curr = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; ++i) {
curr = Math.max(nums[i], curr + nums[i]);
res = Math.max(res, curr);
}
return res;
}
static int[][] dp;
static boolean[][] seen;
public int maxSubArray(int[] nums) {
final int n = nums.length;
dp = new int[n][3];
seen = new boolean[n][3];
return dfs(nums, 0, 0);
}
private static int dfs(int[] nums, int idx, int status) {
if (idx == nums.length) {
return status != 0 ? 0 : (int) -1e9;
}
if (seen[idx][status]) {
return dp[idx][status];
}
int res = (int) -1e9;
if (status == 0) {
res = Math.max(res, dfs(nums, idx + 1, 0));
res = Math.max(res, nums[idx] + dfs(nums, idx + 1, 1));
} else if (status == 1) {
res = Math.max(res, nums[idx] + dfs(nums, idx + 1, 1));
res = Math.max(res, dfs(nums, idx + 1, 2));
} else {
res = Math.max(res, dfs(nums, idx + 1, 2));
}
seen[idx][status] = true;
return dp[idx][status] = res;
}
public int maxSubArrayDC(int[] nums) {
final int n = nums.length;
if (n == 1) {
return nums[0];
}
final int mid = n - 1 >>> 1;
int bestLeft = Integer.MIN_VALUE;
int bestRight = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= 0; i--) {
sum += nums[i];
bestLeft = Math.max(bestLeft, sum);
}
sum = 0;
for (int i = mid + 1; i < n; i++) {
sum += nums[i];
bestRight = Math.max(bestRight, sum);
}
final int left = maxSubArrayDC(Arrays.copyOfRange(nums, 0, mid + 1));
final int right = maxSubArrayDC(Arrays.copyOfRange(nums, mid + 1, n));
return Math.max(Math.max(left, right), bestLeft + bestRight);
}
}