689 Maximum Sum of 3 Non-Overlapping Subarrays

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.利用prefixSum数组，我们可以查到任意区间(i,j)的和，按照我们构造sum数组的方法，subarray(i,j)的和是sum[j + 1] - sum[i]
2.我们可以利用leftIndex数组和rightIndex数组分别保存左边和右边最大subarray sum的起点，如果中间max sum subarray的区间是(i , i + k - 1), 那么左边数组的范围是(0, i - 1), 右边数组的范围(i + k, n - 1)
3.注意当我们求最大右区间时，当前的subarray sum如果大于等于当前最大的subarray sum，我们为了让结果lexicographically small, 我们将其放入对应rightIndex数组里，这个处理和最大左区间不同
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)

688 Knight Probability in Chessboard

691 Stickers to Spell Word

Last modified 2yr ago

Copy link

Contents

689. Maximum Sum of 3 Non-Overlapping Subarrays

1. Question

2. Implementation

3. Time & Space Complexity

689. Maximum Sum of 3 Non-Overlapping Subarrays​

1. Question

2. Implementation

3. Time & Space Complexity

689. Maximum Sum of 3 Non-Overlapping Subarrays