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

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

给你一个整数数组 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]

提示：

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] < 2¹⁶
1 <= k <= floor(nums.length / 3)

相似题目

买卖股票的最佳时机 III

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { } };

cpp 解法, 执行用时: 32 ms, 内存消耗: 22.7 MB, 提交时间: 2023-11-19 00:18:50

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        vector<int> sum;
        int cur = 0;
        for(int i = 0; i < k; ++i){
            cur += nums[i];
        }
        sum.push_back(cur);
        for(int i = k; i < nums.size(); ++i){
            cur += nums[i] - nums[i - k];
            sum.push_back(cur);
        }
        int n = sum.size();
        vector<int> left(n, 0), right(n, n - 1);
        for(int i = 1; i < n; ++i){
            if(sum[i] > sum[left[i - 1]]) left[i] = i;
            else left[i] = left[i - 1];
        }
        for(int i = n - 2; i >= 0; --i){
            if(sum[i] >= sum[right[i + 1]]) right[i] = i;
            else right[i] = right[i + 1];
        }
        int mx = 0;
        vector<int> ans(3);
        for(int i = k; i < n - k; ++i){
            if(mx < sum[i] + sum[left[i - k]] + sum[right[i + k]]){
                mx = sum[i] + sum[left[i - k]] + sum[right[i + k]];
                ans = {left[i - k], i, right[i + k]};
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 20 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-21 14:50:54

func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) {
    var sum1, maxSum1, maxSum1Idx int
    var sum2, maxSum12, maxSum12Idx1, maxSum12Idx2 int
    var sum3, maxTotal int
    for i := k * 2; i < len(nums); i++ {
        sum1 += nums[i-k*2]
        sum2 += nums[i-k]
        sum3 += nums[i]
        if i >= k*3-1 {
            if sum1 > maxSum1 {
                maxSum1 = sum1
                maxSum1Idx = i - k*3 + 1
            }
            if maxSum1+sum2 > maxSum12 {
                maxSum12 = maxSum1 + sum2
                maxSum12Idx1, maxSum12Idx2 = maxSum1Idx, i-k*2+1
            }
            if maxSum12+sum3 > maxTotal {
                maxTotal = maxSum12 + sum3
                ans = []int{maxSum12Idx1, maxSum12Idx2, i - k + 1}
            }
            sum1 -= nums[i-k*3+1]
            sum2 -= nums[i-k*2+1]
            sum3 -= nums[i-k+1]
        }
    }
    return
}

// 背包 + 前缀和
func maxSumOfThreeSubarrays2(nums []int, k int) []int {
    type path struct{
        Val, A, B, C int
    }
    max := func(a,b path) path {
        if a.Val > b.Val {
            return a
        }
        return b
    }

    windows := make([]int, len(nums) - k + 1)
    for i,j,s :=0,0,0; i <= len(nums); i++ {
        if i < k {
            s += nums[i]
        }else{
            windows[j] = s
            j++
            if i < len(nums) {
                s += nums[i] - nums[i - k]
            }
        }
    }

    dp := make([][]path, len(nums) - k + 1)
    for i := 0; i < len(windows); i++{
        dp[i] = make([]path, 3)
        if i == 0 {
            dp[i][0] = path{windows[i], i, 0, 0}
        }else{
            dp[i][0] = max(path{windows[i], i, 0, 0},dp[i-1][0])
        }
        if i >= k {
            dp[i][1] = max(path{dp[i-k][0].Val + windows[i], dp[i-k][0].A, i, 0}, dp[i-1][1])
            if i >= 2 * k {
                dp[i][2] = max(path{dp[i-k][1].Val + windows[i], dp[i-k][1].A,dp[i-k][1].B, i}, dp[i-1][2]) 
            }
        }
    }
    p := path{0, 0, 0, 0}
    for _, paths := range dp {
        if paths[2].Val > p.Val{
            p = paths[2]
        }
    }
    return []int{p.A, p.B, p.C}
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-21 14:50:12

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSumOfThreeSubarrays2 = function(nums, k) {
    var lMax = function(l1, l2){
        if(l1[0] > l2[0])
            return l1
        return l2
    }

    const windows = new Array(nums.length - k + 1)
    for(let i=0,j=0,s=0;i<=nums.length;i++){
        if(i < k)
            s += nums[i]
        else{
            windows[j++] = s
            if(i<nums.length)
                s += nums[i] - nums[i-k]
        }
    }
    const dp = new Array(windows.length)
    for(let i=0;i<dp.length;i++){
        dp[i] = new Array(3)
        for(let j=0;j<3;j++)
            dp[i][j] = [0]
    }
        
    for(let i=0;i<windows.length;i++)
        if(i < k)
            if(i > 0)
                dp[i][0] = lMax([windows[i], i], dp[i-1][0])
            else
                dp[i][0] = [windows[i], i]
        else{
            dp[i][0] = lMax([windows[i], i], dp[i-1][0])
            dp[i][1] = lMax([dp[i-k][0][0]+windows[i], dp[i-k][0][1], i], dp[i-1][1])
            if(i >= 2 * k)
                dp[i][2] = lMax([dp[i-k][1][0] + windows[i], dp[i-k][1][1], dp[i-k][1][2], i], dp[i-1][2])
        }
    let m = 0;
    let ans = new Array(3);
    for(let i=0;i<windows.length;i++)
        if(dp[i][2][0] > m){
            m = dp[i][2][0];
            for(let j=0;j<3;j++)
                ans[j] = dp[i][2][j+1];
        }
    return ans;
};

// 滑动窗口
const maxSumOfThreeSubarrays = (nums, k) => {
    const ans = [0, 0, 0];
    let sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
    let sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
    let sum3 = 0, maxTotal = 0;
    for (let i = k * 2; i < nums.length; ++i) {
        sum1 += nums[i - k * 2];
        sum2 += nums[i - k];
        sum3 += nums[i];
        if (i >= k * 3 - 1) {
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                maxSum1Idx = i - k * 3 + 1;
            }
            if (maxSum1 + sum2 > maxSum12) {
                maxSum12 = maxSum1 + sum2;
                maxSum12Idx1 = maxSum1Idx;
                maxSum12Idx2 = i - k * 2 + 1;
            }
            if (maxSum12 + sum3 > maxTotal) {
                maxTotal = maxSum12 + sum3;
                ans[0] = maxSum12Idx1;
                ans[1] = maxSum12Idx2;
                ans[2] = i - k + 1;
            }
            sum1 -= nums[i - k * 3 + 1];
            sum2 -= nums[i - k * 2 + 1];
            sum3 -= nums[i - k + 1];
        }
    }
    return ans;
}

cpp 解法, 执行用时: 12 ms, 内存消耗: 20.1 MB, 提交时间: 2023-09-21 14:49:32

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
        vector<int> ans;
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.size(); ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans = {maxSum12Idx1, maxSum12Idx2, i - k + 1};
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 4 ms, 内存消耗: 44.6 MB, 提交时间: 2023-09-21 14:48:15

class Solution {
    // 背包
    public int[] maxSumOfThreeSubarrays2(int[] nums, int k) {
        int[] windows = new int[nums.length - k + 1];
        for(int i=0,j=0,s=0;i<=nums.length;i++){
            if(i < k)
                s += nums[i];
            else{
                windows[j++] = s;
                if(i<nums.length)
                    s += nums[i] - nums[i-k];
            }
        }
        int[][][] dp = new int[windows.length][3][1];
        for(int i=0;i<windows.length;i++)
            if(i < k)
                if(i > 0)
                    dp[i][0] = lMax(new int[]{windows[i], i}, dp[i-1][0]);
                else
                    dp[i][0] = new int[]{windows[i], i};
            else{
                dp[i][0] = lMax(new int[]{windows[i], i}, dp[i-1][0]);
                dp[i][1] = lMax(new int[]{dp[i-k][0][0]+windows[i], dp[i-k][0][1], i}, dp[i-1][1]);
                if(i >= 2 * k)
                    dp[i][2] = lMax(new int[]{dp[i-k][1][0] + windows[i], dp[i-k][1][1], dp[i-k][1][2], i}, dp[i-1][2]);
            }
        int m = 0;
        int[] ans = new int[3];
        for(int i=0;i<windows.length;i++)
            if(dp[i][2][0] > m){
                m = dp[i][2][0];
                for(int j=0;j<3;j++)
                    ans[j] = dp[i][2][j+1];
            }
        return ans;
    }

    private int[] lMax(int[] a, int[] b){
        if(a[0] > b[0])
            return a;
        return b;
    }

    // 滑动窗口
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.length; ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 76 ms, 内存消耗: 18.1 MB, 提交时间: 2023-09-21 14:27:30

class Solution:
    # 滑动窗口
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12, maxSum12Idx = 0, 0, ()
        sum3, maxTotal = 0, 0
        for i in range(k * 2, len(nums)):
            sum1 += nums[i - k * 2]
            sum2 += nums[i - k]
            sum3 += nums[i]
            if i >= k * 3 - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = i - k * 3 + 1
                if maxSum1 + sum2 > maxSum12:
                    maxSum12 = maxSum1 + sum2
                    maxSum12Idx = (maxSum1Idx, i - k * 2 + 1)
                if maxSum12 + sum3 > maxTotal:
                    maxTotal = maxSum12 + sum3
                    ans = [*maxSum12Idx, i - k + 1]
                sum1 -= nums[i - k * 3 + 1]
                sum2 -= nums[i - k * 2 + 1]
                sum3 -= nums[i - k + 1]
        return ans
        
    '''
    前缀和 + 背包动态规划
    '''
    def maxSumOfThreeSubarrays2(self, nums: List[int], k: int) -> List[int]:
        def lMax(l1, l2):
            # 根据我们放入这个函数的顺序，可以保证相等的时候我们始终返回坐标字典序小的那一个
            if l1[0] >= l2[0]:
                return l1
            return l2

        presum = [0] + list(accumulate(nums))
        # 每k个求和构成所有可选的连续子数组的和
        windows = [presum[i+k] - presum[i] for i in range(len(nums) - k + 1)]
        # 从windows里选三个数和最大且不相邻
        # dp[i]有三个维度，分别代表选第一个的最大值和坐标，选第二个的最大值和坐标，以及选第三个的最大值和坐标
        dp = [[[0, -1]] * 3 for _ in range(len(windows))]
        for i,w in enumerate(windows):
            # 只有可能选第一个
            if i < k:
                dp[i][0] = lMax(dp[i-1][0], [w, i])
            else:
                dp[i][0] = lMax(dp[i-1][0], [w, i])
                # 维护第二个的最大值, 它由k个前取了第一个的最大值加上取当前的值 和 上一次取第二个的最大值构成
                dp[i][1] = lMax([dp[i-k][0][0] + w, (dp[i-k][0][1],i)], dp[i-1][1])
                # 只有2k以后才有可能选第三个，维护第三个的最大值, 它由k个前取了第二个的最大值加上取当前的值 和 上一次取第三个的最大值构成
                if i >= 2 * k:
                    dp[i][2] = lMax([dp[i-k][1][0] + w, (dp[i-k][1][1][0],dp[i-k][1][1][1],i)], dp[i-1][2])
        m, ans = 0, None
        for d in dp:
            if d[2][0] > m:
                m = d[2][0]
                ans = d[2][1]
        return ans

上一题

下一题

详情