1
2
3
4
| 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.
|
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
| class Solution {
/**
* cache[i] = sum(nums[i],...,nums[i+k])
* int max_idx(int[] arr, int i, int j) -> 数组arr在[i,j]范围内的最大值的第一次出现的位置
* left[i] = max_idx(cache, 0, i)
* right[i] = max_idx(cache, i, cache.lenght - 1)
*
* @param nums
* @param k
* @return
*/
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] cache = new int[nums.length - k + 1];
int[] left = new int[nums.length - k + 1];
int[] right = new int[nums.length - k + 1];
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
cache[0] = sum;
for (int i = 1; i < cache.length; i++) {
int v = cache[i] = sum = sum + nums[i + k - 1] - nums[i - 1];
if (v > cache[left[i - 1]]) {
left[i] = i;
} else {
left[i] = left[i - 1];
}
}
right[right.length - 1] = right.length - 1;
for (int i = cache.length - 2; i >= 0; i--) {
if (cache[i] >= cache[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
int interval = k << 1;
int[] res = new int[]{0, k, interval};
int max = Integer.MIN_VALUE;
int max_m = cache.length - k;
for (int m = k; m < max_m; m++) {
int v = cache[left[m - k]] + cache[m] + cache[right[m + k]];
if (v > max) {
max = v;
res[0] = left[m - k];
res[1] = m;
res[2] = right[m + k];
}
}
return res;
}
}
|