How do I handle overlapping subarrays for this problem?

Use prefix sums and track the maximum sum for subarrays ending before the current index to ensure no overlap occurs.

Can the subarrays be in any order?

Yes, evaluate both orders of firstLen and secondLen subarrays and take the maximum sum among them.

Why is state transition dynamic programming useful here?

It efficiently combines prefix sums and maximum sums for valid subarray placements without redundant computations.

What is the time complexity for this approach?

Computing prefix sums and iterating to evaluate subarrays gives O(n) time complexity, with n being the length of nums.

What edge cases should I test?

Test small arrays, subarrays at the beginning or end, and cases where firstLen equals secondLen to ensure non-overlapping constraints are respected.

#1031

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen ，请你找出并返回两个无重叠子数组中元素的最大和，长度分别为 firstLen 和 secondLen 。长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是无…

数组动态规划滑动窗口

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

lightbulb

解题思路

方法一：前缀和 + 枚举

我们先预处理得到数组 nums 的前缀和数组 $s$ ，其中 $s[i]$ 表示 $nums$ 中前 $i$ 个元素的和。

接下来，我们分两种情况枚举：

假设 $firstLen$ 个元素的子数组在 $secondLen$ 个元素的子数组的左边，那么我们可以枚举 $secondLen$ 个元素的子数组的左端点 $i$ ，用变量 $t$ 维护左边 $firstLen$ 个元素的子数组的最大和，那么答案就是 $t + s[i + secondLen] - s[i]$ 。枚举完所有的 $i$ ，就可以得到候选答案。

假设 $secondLen$ 个元素的子数组在 $firstLen$ 个元素的子数组的左边，那么我们可以枚举 $firstLen$ 个元素的子数组的左端点 $i$ ，用变量 $t$ 维护左边 $secondLen$ 个元素的子数组的最大和，那么答案就是 $t + s[i + firstLen] - s[i]$ 。枚举完所有的 $i$ ，就可以得到候选答案。

最后，我们取两种情况下的候选答案的最大值即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = t = 0
        i = firstLen
        while i + secondLen - 1 < n:
            t = max(t, s[i] - s[i - firstLen])
            ans = max(ans, t + s[i + secondLen] - s[i])
            i += 1
        t = 0
        i = secondLen
        while i + firstLen - 1 < n:
            t = max(t, s[i] - s[i - secondLen])
            ans = max(ans, t + s[i + firstLen] - s[i])
            i += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) for computing prefix sums and iterating through the array to find optimal subarrays, with n being the length of nums. Space complexity is O(n) to store prefix sums and DP states.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Prefers using prefix sums to avoid repeated subarray sum calculations.
question_mark
Checks if you handle both subarray orderings for firstLen and secondLen.
question_mark
Wants attention to non-overlapping constraint in state updates.

warning

常见陷阱

外企场景

error
Ignoring the non-overlapping constraint between the two subarrays.
error
Only checking one ordering of firstLen and secondLen, missing better sums.
error
Incorrectly computing subarray sums without prefix sums, causing timeouts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximum sum of k non-overlapping subarrays of different lengths.
arrow_right_alt
Find subarrays with a maximum product instead of sum while keeping them non-overlapping.
arrow_right_alt
Allow subarrays to overlap partially with a penalty function instead of strict exclusion.

help

常见问题

外企场景

继续练习

#978 最长湍流子数组 #718 最长重复子数组 #689 三个无重叠子数组的最大和