0689. Maximum Sum of 3 Non-Overlapping Subarrays

题目信息

题号:

0689

难度:

Hard

主题:

正整数数组、三个固定长度窗口、互不重叠、字典序并列规则

原题:

LeetCode 0689

重点:

必须选择恰好三个长度为 k 的连续子数组、窗口不能共享位置、最大化三段总和、并列时返回字典序最小的起点数组

题目重述

给定正整数数组 nums 和整数 k,选择三个长度都恰好为 k 的连续子数组。三段不能重叠,返回它们按从左到右排列的零基起始下标 [i, j, l],使三段元素总和最大。

若多个下标三元组得到相同最大总和,返回字典序最小的一个,即先比较 i,再比较 j,最后比较 l。nums.length 位于 [3, 2 * 10^4],元素为正整数,1 <= k <= nums.length/3。

自建示例

最优窗口分布在数组三处:

输入:nums = [4,1,3,2,8,1,7,2,6],k = 2
输出:[0,3,6]
解释:三段 [4,1]、[2,8]、[7,2] 的和分别为 5、10、9,总和 24,大于其他合法组合。

多个最大方案时取字典序更小者:

输入:nums = [5,5,5,5],k = 1
输出:[0,1,2]
解释:任意三个不同位置的单元素窗口总和都是 15,因此返回起点三元组中字典序最小的 [0,1,2]。