What is the main technique used to solve the Maximum Sum of 3 Non-Overlapping Subarrays problem?

The solution relies on dynamic programming combined with sliding window and prefix sum techniques to calculate subarray sums and track the optimal results.

How does lexicographical order impact the solution?

When there are multiple subarrays with the same sum, the lexicographically smallest starting indices are selected as the final answer.

What is the time complexity of this problem?

The time complexity of the solution is O(n + k), where n is the length of the array and k is the subarray length.

How does the sliding window technique apply to this problem?

The sliding window technique helps efficiently compute the sum of all subarrays of length k by maintaining a running sum as the window slides across the array.

What are common mistakes to avoid when solving this problem?

Common mistakes include failing to handle overlapping subarrays properly, not considering lexicographical order for multiple solutions, and inefficient space usage.

#689

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和最大的子数组，并返回这三个子数组。以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。示例 1：输入： nums = [1,2,…

数组动态规划滑动窗口前缀和

题目描述

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 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)

lightbulb

解题思路

方法一：滑动窗口

滑动窗口，枚举第三个子数组的位置，同时维护前两个无重叠子数组的最大和及其位置。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(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

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        s = s1 = s2 = s3 = 0
        mx1 = mx12 = 0
        idx1, idx12 = 0, ()
        ans = []
        for i in range(k * 2, len(nums)):
            s1 += nums[i - k * 2]
            s2 += nums[i - k]
            s3 += nums[i]
            if i >= k * 3 - 1:
                if s1 > mx1:
                    mx1 = s1
                    idx1 = i - k * 3 + 1
                if mx1 + s2 > mx12:
                    mx12 = mx1 + s2
                    idx12 = (idx1, i - k * 2 + 1)
                if mx12 + s3 > s:
                    s = mx12 + s3
                    ans = [*idx12, i - k + 1]
                s1 -= nums[i - k * 3 + 1]
                s2 -= nums[i - k * 2 + 1]
                s3 -= nums[i - k + 1]
        return ans

speed

复杂度分析

指标	值
时间	O(n + k)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate can identify and use sliding window and dynamic programming efficiently.
question_mark
Candidate understands the importance of lexicographical order in handling multiple solutions.
question_mark
Candidate can optimize space usage while calculating results for large input sizes.

warning

常见陷阱

外企场景

error
Failing to properly handle overlapping subarrays, leading to incorrect subarray selections.
error
Not considering the lexicographically smallest answer when multiple solutions have the same sum.
error
Overcomplicating the problem with unnecessary space usage or inefficient algorithms.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than three subarrays to be selected, testing the flexibility of the approach.
arrow_right_alt
Changing the value of k to test how the approach scales with different subarray sizes.
arrow_right_alt
Introducing constraints on the array values to test the robustness of the algorithm.

help

常见问题

外企场景

继续练习

#713 乘积小于 K 的子数组 #718 最长重复子数组 #862 和至少为 K 的最短子数组