689. 三个无重叠子数组的最大和

难度困难324收藏分享切换为英文接收动态反馈

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。

以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

示例 1：

输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        const int n = nums.size(); 
        // 前缀和
        vector<long long> sum(n+1, 0);  for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + nums[i-1]; 
        // 计算最优值
        vector<vector<long long>> f(n+2, vector<long long>(4, 0)); 
        for (int i = n - k + 1; i >= 1; i--){
            for (int j = 1; j < 4; j++){ 
                f[i][j] = std::max(f[i+1][j], sum[i+k-1] - sum[i-1] + f[i+k][j-1]);   
            }
        }
        // 从最优值和最终状态开始回溯 (背包回溯方案)。
        vector<int> ans; 
        int i = 1, j = 3; 
        // 在决定第几个枚举点? 
        while (j > 0){ 
            // 最优值 f[i][j] 一定从两个状态转移过来 : f[i+1][j] 或者 sum[i...i+k-1] + f[i+k][j-1] 
            // (1) 如果 nums[i] 无贡献，则一定有 f[i+1][j] 更大
            if (f[i+1][j] > f[i+k][j-1] + sum[i+k-1] - sum[i-1]){  i++;  }
            // (2) 如果 nums[i] 被选择，则一定有 sum[i...i+k-1] + f[i+k][j-1] 更大。
            else{
                ans.push_back(i-1);  // 注意我们的索引从1开始。
                i += k; // 选取 nums[i] 后，只能继续从 nums[i+k...] 继续模拟取后面的点。
                j--; 
            }
        }
        return ans;
    }   
};