Leetcode
Dynamic Programming
689 Maximum Sum of 3 Non-Overlapping Subarrays

1. Question

In a given arraynumsof positive integers, find three non-overlapping subarrays with maximum sum.
Each subarray will be of sizek, and we want to maximize the sum of all3*kentries.
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:
1
Input: [1,2,1,2,6,7,5,1], 2
2
3
Output: [0, 3, 5]
4
5
Explanation:
6
Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
7
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
Copied!
Note:
nums.lengthwill be between 1 and 20000.
nums[i]will be between 1 and 65535.k
will be between 1 and floor(nums.length / 3).

2. Implementation

(1) DP
思路:
  1. 1.
    利用prefixSum数组,我们可以查到任意区间(i,j)的和,按照我们构造sum数组的方法,subarray(i,j)的和是sum[j + 1] - sum[i]
  2. 2.
    我们可以利用leftIndex数组和rightIndex数组分别保存左边和右边最大subarray sum的起点,如果中间max sum subarray的区间是(i , i + k - 1), 那么左边数组的范围是(0, i - 1), 右边数组的范围(i + k, n - 1)
  3. 3.
    注意当我们求最大右区间时,当前的subarray sum如果大于等于当前最大的subarray sum,我们为了让结果lexicographically small, 我们将其放入对应rightIndex数组里,这个处理和最大左区间不同
  4. 4.
    中间区间的 i介于 (i, i + k - 1)之间,由于i + k - 1 <= n - k - 1 => i <= n - 2*k, 所以中间区间的起点在(k, n - 2 * k)
1
class Solution {
2
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
3
int[] res = new int[3];
4
5
if (nums == null || nums.length < 3 * k) {
6
return res;
7
}
8
9
int n = nums.length;
10
int[] sum = new int[n + 1];
11
12
for (int i = 1; i <= n; i++) {
13
sum[i] = sum[i - 1] + nums[i - 1];
14
}
15
16
// the subarray sum between nums[i...j] will be sum[j + 1] - sum[i], i and j both starts with 0
17
18
int[] leftIndex = new int[n];
19
int[] rightIndex = new int[n];
20
21
int curMaxSum = sum[k] - sum[0];
22
23
// Find the start point of max left sum subarray
24
// Since we have have calculated the sum of subarray(0, k - 1), we start at 1 here
25
for (int i = 1; i <= n - k; i++) {
26
if (sum[i + k] - sum[i] > curMaxSum) {
27
leftIndex[i] = i;
28
curMaxSum = sum[i + k] - sum[i];
29
}
30
else {
31
leftIndex[i] = leftIndex[i - 1];
32
}
33
}
34
35
curMaxSum = sum[n] - sum[n - k];
36
rightIndex[n - k] = n - k;
37
38
// Find the start point of max right sum subarray
39
// Since we have have calculated the sum of subarray(n - k, n - 1), we start at n - k - 1 here
40
for (int i = n - k - 1; i >= 0; i--) {
41
// we use ">=" here because we try to make the answer lexicographically smaller.
42
// i.e. when there are subarray sum equal to the curMaxSum, we try to make the start point
43
// as small as possible
44
if (sum[i + k] - sum[i] >= curMaxSum) {
45
rightIndex[i] = i;
46
curMaxSum = sum[i + k] - sum[i];
47
}
48
else {
49
rightIndex[i] = rightIndex[i + 1];
50
}
51
}
52
53
// Find the start point of the max sum subarray in the middle
54
int maxSum = Integer.MIN_VALUE;
55
56
for (int i = k; i <= n - 2 * k; i++) {
57
int leftStart = leftIndex[i - k], rightStart = rightIndex[i + k];
58
59
curMaxSum = sum[leftStart + k] - sum[leftStart] + sum[rightStart + k] - sum[rightStart] + sum[i + k] - sum[i];
60
61
if (curMaxSum > maxSum) {
62
maxSum = curMaxSum;
63
res[0] = leftStart;
64
res[1] = i;
65
res[2] = rightStart;
66
}
67
}
68
return res;
69
}
70
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)