-
Notifications
You must be signed in to change notification settings - Fork 81
/
MaximumSumOf3NonOverlappingSubarrays689.java
100 lines (89 loc) 路 2.93 KB
/
MaximumSumOf3NonOverlappingSubarrays689.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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
* In a given array nums of positive integers, find three non-overlapping
* subarrays with maximum sum.
*
* Each subarray will be of size k, and we want to maximize the sum of all
* 3*k entries.
*
* Return the result as a list of indices representing the starting position of
* each interval (0-indexed). If there are multiple answers, return the
* lexicographically smallest one.
*
* Example:
* Input: [1,2,1,2,6,7,5,1], 2
* Output: [0, 3, 5]
* Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting
* indices [0, 3, 5].
*
* We could have also taken [2, 1], but an answer of [1, 3, 5] would be
* lexicographically larger.
*
* Note:
* nums.length will be between 1 and 20000.
* nums[i] will be between 1 and 65535.
* k will be between 1 and floor(nums.length / 3).
*
*/
public class MaximumSumOf3NonOverlappingSubarrays689 {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] sums = new int[nums.length+1];
for (int i=1; i<=nums.length; i++) sums[i] = sums[i-1] + nums[i-1];
int[][] dp = new int[4][nums.length+1];
boolean[][] choose = new boolean[3][nums.length];
for (int i=1; i<=3; i++) {
int start = i * k;
for (int j=start; j<=nums.length; j++) {
int pre = dp[i][j-1];
int cur = dp[i-1][j-k] + sums[j] - sums[j-k];
dp[i][j] = Math.max(cur, pre);
if (cur > pre) choose[i-1][j-1] = true;
}
}
int[] res = new int[3];
int i = 2;
int j = nums.length-1;
while (i >= 0) {
while (choose[i][j] == false) j--;
res[i] = j-k+1;
i--;
j = j-k;
}
return res;
}
/**
* https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/
*/
public int[] maxSumOfThreeSubarrays2(int[] nums, int K) {
//W is an array of sums of windows
int[] W = new int[nums.length - K + 1];
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= K) sum -= nums[i-K];
if (i >= K-1) W[i-K+1] = sum;
}
int[] left = new int[W.length];
int best = 0;
for (int i = 0; i < W.length; i++) {
if (W[i] > W[best]) best = i;
left[i] = best;
}
int[] right = new int[W.length];
best = W.length - 1;
for (int i = W.length - 1; i >= 0; i--) {
if (W[i] >= W[best]) best = i;
right[i] = best;
}
int[] ans = new int[]{-1, -1, -1};
for (int j = K; j < W.length - K; j++) {
int i = left[j - K], k = right[j + K];
if (ans[0] == -1 || W[i] + W[j] + W[k] >
W[ans[0]] + W[ans[1]] + W[ans[2]]) {
ans[0] = i;
ans[1] = j;
ans[2] = k;
}
}
return ans;
}
}