Medium

题目描述

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠子数组中元素的最大和，子数组长度分别为 firstLen 和 secondLen。

长度为 firstLen 的子数组可以出现在长度为 secondLen 的子数组之前或之后，但二者必须是不重叠的。

子数组是数组的一个连续部分。

示例 1：

输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：其中一种选择方案是长度为 1 的子数组 [9] 和长度为 2 的子数组 [6,5]。

示例 2：

输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：其中一种选择方案是长度为 3 的子数组 [3,8,1] 和长度为 2 的子数组 [8,9]。

示例 3：

输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：其中一种选择方案是长度为 4 的子数组 [5,6,0,9] 和长度为 3 的子数组 [0,3,8]。

提示：

  • 1 <= firstLen, secondLen <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

解题思路

解题思路

这道题要求找出两个不重叠子数组的最大和，可以用动态规划思想结合滑动窗口来解决。

核心思路是分两种情况考虑：

  1. 长度为 firstLen 的子数组在前，长度为 secondLen 的子数组在后
  2. 长度为 secondLen 的子数组在前，长度为 firstLen 的子数组在后

对于每种情况，我们可以：

  • 使用滑动窗口计算所有可能的子数组和
  • 维护当前位置之前最大的子数组和
  • 对于当前位置的子数组，找到它之前的最佳子数组组合

具体实现时，我们定义一个辅助函数来处理"长度为L的子数组在前，长度为M的子数组在后"的情况。遍历所有可能的第二个子数组位置，同时维护第一个子数组的最大值，从而得到最优组合。

最终答案是两种情况的最大值。这种方法避免了暴力枚举所有可能的子数组组合，时间复杂度为O(n)。

(推荐解法)：动态规划 + 滑动窗口，时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
    }
    
private:
    int helper(vector<int>& nums, int L, int M) {
        int n = nums.size();
        
        // 计算第一个长度为L的子数组的和
        int sumL = 0;
        for (int i = 0; i < L; i++) {
            sumL += nums[i];
        }
        
        // 计算第一个长度为M的子数组的和（从位置L开始）
        int sumM = 0;
        for (int i = L; i < L + M; i++) {
            sumM += nums[i];
        }
        
        int maxL = sumL;  // 当前位置之前长度为L的子数组的最大和
        int result = maxL + sumM;
        
        // 滑动窗口，同时维护maxL和sumM
        for (int i = L + M; i < n; i++) {
            // 更新长度为M的子数组和
            sumM = sumM - nums[i - M] + nums[i];
            
            // 更新长度为L的子数组和
            sumL = sumL - nums[i - M - L] + nums[i - M];
            
            // 更新maxL
            maxL = max(maxL, sumL);
            
            // 更新结果
            result = max(result, maxL + sumM);
        }
        
        return result;
    }
};

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        def helper(L, M):
            # L在前，M在后
            n = len(nums)
            
            # 计算第一个长度为L的子数组的和
            sum_L = sum(nums[:L])
            
            # 计算第一个长度为M的子数组的和（从位置L开始）
            sum_M = sum(nums[L:L+M])
            
            max_L = sum_L  # 当前位置之前长度为L的子数组的最大和
            result = max_L + sum_M
            
            # 滑动窗口，同时维护max_L和sum_M
            for i in range(L + M, n):
                # 更新长度为M的子数组和
                sum_M = sum_M - nums[i - M] + nums[i]
                
                # 更新长度为L的子数组和
                sum_L = sum_L - nums[i - M - L] + nums[i - M]
                
                # 更新max_L
                max_L = max(max_L, sum_L)
                
                # 更新结果
                result = max(result, max_L + sum_M)
            
            return result
        
        return max(helper(firstLen, secondLen), helper(secondLen, firstLen))

public class Solution {
    public int MaxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.Max(Helper(nums, firstLen, secondLen), Helper(nums, secondLen, firstLen));
    }
    
    private int Helper(int[] nums, int L, int M) {
        int n = nums.Length;
        
        // 计算第一个长度为L的子数组的和
        int sumL = 0;
        for (int i = 0; i < L; i++) {
            sumL += nums[i];
        }
        
        // 计算第一个长度为M的子数组的和（从位置L开始）
        int sumM = 0;
        for (int i = L; i < L + M; i++) {
            sumM += nums[i];
        }
        
        int maxL = sumL;  // 当前位置之前长度为L的子数组的最大和
        int result = maxL + sumM;
        
        // 滑动窗口，同时维护maxL和sumM
        for (int i = L + M; i < n; i++) {
            // 更新长度为M的子数组和
            sumM = sumM - nums[i - M] + nums[i];
            
            // 更新长度为L的子数组和
            sumL = sumL - nums[i - M - L] + nums[i - M];
            
            // 更新maxL
            maxL = Math.Max(maxL, sumL);
            
            // 更新结果
            result = Math.Max(result, maxL + sumM);
        }
        
        return result;
    }
}

var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    const helper = (L, M) => {
        const n = nums.length;
        
        // 计算第一个长度为L的子数组的和
        let sumL = 0;
        for (let i = 0; i < L; i++) {
            sumL += nums[i];
        }
        
        // 计算第一个长度为M的子数组的和（从位置L开始）
        let sumM = 0;
        for (let i = L; i < L + M; i++) {
            sumM += nums[i];
        }
        
        let maxL = sumL;  // 当前位置之前长度为L的子数组的最大和
        let result = maxL + sumM;
        
        // 滑动窗口，同时维护maxL和sumM
        for (let i = L + M; i < n; i++) {
            // 更新长度为M的子数组和
            sumM = sumM - nums[i - M] + nums[i];
            
            // 更新长度为L的子数组和
            sumL = sumL - nums[i - M - L] + nums[i - M];
            
            // 更新maxL
            maxL = Math.max(maxL, sumL);
            
            // 更新结果
            result = Math.max(result, maxL + sumM);
        }
        
        return result;
    };
    
    return Math.max(helper(firstLen, secondLen), helper(secondLen, firstLen));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次遍历为O(n)
空间复杂度O(1)只使用了常数个额外变量