原文链接: https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays

英文原文

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

 

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

 

Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

中文题目

给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。

每个子数组的长度为k，我们要使这3*k个项的和最大化。

返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。

示例:

输入: [1,2,1,2,6,7,5,1], 2
输出: [0, 3, 5]
解释: 子数组 [1, 2], [2, 6], [7, 5] 对应的起始索引为 [0, 3, 5]。
我们也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

注意:

• nums.length的范围在[1, 20000]之间。
• nums[i]的范围在[1, 65535]之间。
• k的范围在[1, floor(nums.length / 3)]之间。

通过代码

官方题解

方法一：

用一个数组 W 去考虑每个间隔的和，其中每个间隔都是给定的长度 K。要创建 W，我们可以使用前缀和，或者将间隔的和管理为沿数组滑动的窗口。

我们讨论如何简化问题：给定数组 W 和整数 W，i + K <= j 和 j + K <= k 的索引 (i, j, k) 的字典最小元组是什么，它使 W[i]+W[j]+W[k] 最大化？

算法：

算法：

• 假设我们固定了 j。我们想知道在 $i \in [0, j-K]$ 和 $k \in [j+K, \text{len}(W)-1]$ 之间的间隔，其中 $W[i]$ 和 $W[k]$ 最大值是第一次出现。（是指较小的索引）。
• 我们可以用动态规划来解决这些问题。例如，如果我们知道 $i$ 在 $[0，5]$ 上 $W[i]$ 是最大值，然后在 $[0，6]$ 上，若 $[0，6]$ 更大，那么我们将设置 best = 6。
• 在结尾处，left[z] 将是第一个出现在间隔 $i \in [0, z]$ 上的 W[i] 的最大值，right[z] 是第一个出现在 $i \in [z, \text{len}(W) - 1]$ 上W[i] 的最大值。这意味着对于某些选择 j，答案必须是 (left[j-K], j, right[j+K]) 其中一个。我们选取产生最大 W[i] + W[j] + W[k] 的答案。

复杂度分析

• 时间复杂度：$O(N)$。其中 $N$ 是数组的长度。每个循环的步数都以 $N$ 为界，并且执行 $O(1)$ 工作。
• 空间复杂度：$O(N)$，W，left，right 都需要 $O(N)$ 内存。

统计信息

通过次数	提交次数	AC比率
3499	7108	49.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
买卖股票的最佳时机 III	困难