目录

0689:三个无重叠子数组的最大和(★★)

力扣第 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 * 104
  • 1 <= nums[i] < 216
  • 1 <= k <= floor(nums.length / 3)

相似问题:

分析

令 A[i] 代表 sum(nums[i:i+k]),问题转为求满足 x+k<=y<=z-k 的最大的 A[x]+A[y]+A[z]。

那么遍历 y,求 max(A[:y-k+1])+y+max(A[y+k:]) 即可。

令 left[i] 代表 max(A[:i+1]),right[i] 代表 max(A[i:]),都可以 O(N) 递推得到。

因为要返回下标位置,所以修改下,令 left 和 right 返回最大值对应的最小下标即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
    pre = list(accumulate([0]+nums))
    A = [pre[i+k]-pre[i] for i in range(len(pre)-k)]
    n = len(A)
    left, right = list(range(n)), list(range(n))
    for i in range(1, n):
        left[i] = i if A[i]>A[left[i-1]] else left[i-1]
    for i in range(n-2, -1, -1):
        right[i] = i if A[i]>=A[right[i+1]] else right[i+1]
    i = max(range(k, n-k), key=lambda i: A[left[i-k]]+A[i]+A[right[i+k]])
    return [left[i-k], i, right[i+k]]

80 ms