leetcode 689

问题

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:

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.

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).

分析

我们可以先确定中间的区间 [i, i+k-1] (k <= i <= n-2k)，那么左边的区间就在 [0, i-1] 中取，右边的区间就在 [i+k, n-1] 中取。于是，我们可以令 posLeft[i] 表示，从[0, i] 选择 k 个连续数，使其最大的起始坐标。posRight[i] 表示，从 [i, n-1] 选择 k 个连续数，使其和最大的起始坐标。然后，我们尝试中间区间每一个可能的起始坐标。

代码1

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
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> posLeft(n, 0), posRight(n, n-k), ans(3, 0);
        
        for (int i = 1; i < n; ++i) nums[i] += nums[i-1];
        
        for (int i = k, tot = nums[k-1]; i < n-2*k; ++i) {
            if (nums[i] - nums[i-k] > tot) {
                posLeft[i] = i-k+1;
                tot = nums[i]-nums[i-k];
            } else {
                posLeft[i] = posLeft[i-1];
            }
        }
        for (int i = n-k-1, tot = nums[n-1]-nums[n-k-1]; i >= 2*k; --i) {
            if (nums[i+k-1] - nums[i-1] >= tot) {
                posRight[i] = i;
                tot = nums[i+k-1]-nums[i-1];
            } else {
                posRight[i] = posRight[i+1];
            }
        }
        for (int i = k, tot = 0; i <= n-2*k; ++i) {
            int l = posLeft[i-1];
            int r = posRight[i+k];
            int sum = nums[r+k-1]-nums[r-1]+nums[i+k-1]-nums[i-1]+nums[l+k-1]-(l > 0? nums[l-1]: 0);
            if (sum > tot) {
                ans = {l, i, r};
                tot = sum;
            }
        }
        return ans;
    }
};

代码2

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
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(3, vector<int>(n+1, 0));
        vector<vector<int>> index(3, vector<int>(n+1, 0));

        for (int i = 1; i < n; ++i) nums[i] += nums[i-1];

        auto getSum = [&nums](int x, int k) -> int {
            return x == 0? nums[x+k-1]: nums[x+k-1]-nums[x-1];
        };
        for (int i = n-k; i >= 0; --i) {
            dp[0][i] = dp[0][i+1];
            index[0][i] = index[0][i+1];
            if (getSum(i, k) >= dp[0][i+1]) {
                dp[0][i] = getSum(i, k);
                index[0][i] = i;
            }
        }
        for (int i = n-2*k; i >= 0; --i) {
            dp[1][i] = dp[1][i+1];
            index[1][i] = index[1][i+1];
            if (getSum(i, k) + dp[0][i+k] >= dp[1][i+1]) {
                dp[1][i] = getSum(i, k) + dp[0][i+k];
                index[1][i] = i;
            }
        }
        for (int i = n-3*k; i >= 0; --i) {
            dp[2][i] = dp[2][i+1];
            index[2][i] = index[2][i+1];
            if (getSum(i, k) + dp[1][i+k] >= dp[2][i+1]) {
                dp[2][i] = getSum(i, k) + dp[1][i+k];
                index[2][i] = i;
            }
        }
        int a = index[2][0];
        int b = index[1][a+k];
        int c = index[0][b+k];
        return {a,b,c};
    }
};