前几天我在 Go 技术群里看到有人发了一道题标题写着“最大子数组总值Ⅱ”底下跟着一串描述给定长度 n 的整数数组 nums还有一个整数 k要挑出恰好 k 个互不相同的非空连续区间允许重叠但不能重复选同一对左右端点最后让这些区间的和加起来最大。第一眼看过去这不就是“最大子数组和”的扩展版吗但真动手做才发现这里面坑不少。尤其是“允许重叠”这四个字直接把很多熟悉的套路给堵死了。今天我就用 Go 语言完整拆一遍这道题讲清楚为什么不能用普通贪心以及最终为什么应该把它当成“求所有子数组和的前 k 大”来做。整个过程会包含完整代码、复杂度分析和几个我实际踩过的边界坑适合正在刷题、准备算法面试或者想练 Go 语言基础的朋友。1. 题目到底在问什么1.1 从“最大子数组和”到“最大子数组总值Ⅱ”先回忆一下最经典的“最大子数组和”给你一个数组找一个连续子区间让它的和最大。Kadane 算法一遍 O(n) 就能解决。但这道题完全不同。它要求的是选 k 个区间每个区间都可以贡献自己的区间和最后把这些区间和全部加起来。这意味着同一个位置上的数可以被多个区间重复计算。比如数组是 [10, 9, 8, 7, 6]k2如果每个区间都必须互不重叠那最多只能选 [0,1] 和 [2,4]总和是 192140但题目允许重叠最优解是选 [0,4]和 40和 [0,3]和 34总和是 74。看明白这个例子你就知道为什么不能直接套用“不重叠区间”或者“Kadane 贪心”的思路了。允许重叠后最优区间往往不是互斥的而是一层层嵌套、错开的。问题的本质一下子变了我们其实是在一个巨大的“所有子数组和”集合里挑出最大的 k 个不同的值相加。1.2 第一直觉为什么翻车很多人第一反应是用贪心先找到全局最大子数组加入答案然后在剩余部分继续找最大子数组。这个思路适合“不重叠”的情况因为选完一个区间后问题可以断开成左右两边。但允许重叠后选了 [0,4]还可以继续选 [0,3]、[1,4] 这种和它高度重叠的次优区间而这两个候选在贪心“断开”的过程中会被丢掉。还有人想用动态规划。设 dp[i][j] 表示前 i 个位置选 j 个区间的最大总和看起来可行但一旦允许重叠转移时很难避免同一个区间被重复选两次。因为 dp[i][j-1] 里可能已经包含了那个“新加入的区间”。要强行去重得记录更多状态状态数量爆炸实际不可行。所以这道题的关键是换一个视角所有子数组的区间和天然就是一堆数值我们只是需要高效地找出其中最大的 k 个并且不能重复。这样想问题就清晰了。1.3 区间与前缀和的对应关系区间和通常用前缀和来算。定义一个长度为 n1 的前缀数组 prepre[0] 0pre[i1] pre[i] nums[i]。那么任意子数组 nums[l..r] 的和就等于 pre[r1] - pre[l]。这里我把左端点记作 L右端点对应前缀下标记作 R那么必须满足 0 ≤ L R ≤ n。每个子数组都唯一对应一对 (L, R)反过来也对。这个一一对应关系非常重要因为它保证了后面算法里不会重复计数。2. 核心思路把整个问题变成 Top-K 子区间和问题2.1 固定左端点问题立刻降维如果我们固定一个左端点 L那么所有以 L 为起点的子数组右端点 R 可以取 L1 到 n 的任意值。它们的区间和是 pre[R] - pre[L]。在这个式子里pre[L] 是个常数想让区间和最大就要让 pre[R] 最大。所以对于固定 L它的最优右端点就是 pre 在 [L1, n] 范围内的最大值所在位置。这个观察非常关键。它把“枚举一个区间”变成了“在一个连续下标范围里查 pre 的最大值”。而查询区间最大值就可以用 ST 表或者线段树做到 O(1) 或 O(log n)。2.2 用大根堆维护每个左端点的最佳候选我们给每个左端点 L 都维护一个“当前还没被选过的最佳区间”。这可以用一个大根堆来实现堆里每个节点代表一个候选方案节点里至少存这几样东西左端点 L右端点可选的前缀下标范围 [lo, hi]在这个范围内 pre 最大的位置 best这个候选区间的和 val pre[best] - pre[L]。初始化时对于每个 L可选范围都是 [L1, n]算出各自的 best 和 val全部丢进堆。这时堆顶就是所有区间中总和最大的那个区间。接下来循环 k 次每次从堆里弹出堆顶这个区间的和加入答案。然后因为区间 (L, best) 已经被选过了而它原本所在的候选范围 [lo, hi] 中以 best 为分界点剩余的右端点候选被分成了两段左边一段 [lo, best-1]右边一段 [best1, hi]。这两个范围里各有一个最优右端点。把它们分别作为新的候选节点重新丢进堆。这样左端点 L 剩下的“最优未选区间”仍然在堆里并且这个分裂过程保证了每个右端点只会作为 best 被弹出一次。2.3 候选区间的“分裂”为什么能保证不重不漏这个思想其实来源于一道著名的题通常叫“超级钢琴”在一个数组里求长度在某范围内的前 k 大子段和。核心就是“区间分裂”加“优先队列”。要理解它为什么不重不漏我们可以这样想固定 L 之后所有可选的 R 组成了一个连续区间。第一次我们从整个区间里找到最优的 R。这个最优 R 一旦被弹出它就被“拿走”了剩下的 R 集合自然分裂成左右两部分。每一部分仍然是一个连续区间所以我们可以继续用 RMQ 找到这一部分的最优 R。重复这个过程相当于按 pre[R] 从大到小把 [L1, n] 里的所有下标都访问一遍。因为堆里同时存着所有左端点各自当前最优的候选所以每次弹出的都是全局剩余区间里总和最大的那一个。这正好就是“所有子数组和的前 k 大”。区间互不相同是天然成立的因为每个候选节点代表一个具体的 (L, R)只会被弹出一次。区间重叠也没有任何限制因为它们只是共享元素并不影响各自区间和的数值计算。2.4 为什么这个问题可以用 Top-K 框架统一解决当你把问题理解成“前 k 大子区间和”后“允许重叠”“互不相同”这些条件都变得非常自然了。我们根本不关心两个区间是否重叠只是按数值从大到小取区间保证不取同一个区间即可。这种 Top-K 框架的适用范围很广。除了通常限制区间长度的超级钢琴题很多“选 k 个结构对象最大化权值”的问题都可以用“优先队列 候选区间分裂”来解决。核心是先定义清楚每个对象怎么唯一表示、每个候选的“剩余最优”怎么快速求出来。3. Go 语言完整实现3.1 环境准备与数据结构设计我默认你已经装好了 Go 环境能正常跑go run main.go。如果还没装可以先去官网下载对应系统版本配置好 GOPATH 或者直接使用模块模式这属于 go 语言环境配置的基础操作这里不展开。这道题需要两个核心数据结构ST 表用于在 [lo, hi] 范围内快速查询 pre 最大值对应的下标大根堆用于维护所有候选区间。为什么用 ST 表而不是线段树因为这道题只有区间最大值查询没有更新操作ST 表实现更简单查询 O(1)而且代码量少很多。唯一要注意的是 ST 表预处理需要 O(n log n) 的内存和空间n 2e5 时大约 360 万个 int完全可以接受。堆的话Go 的标准库container/heap需要自己实现接口。我定义了一个结构体Item里面包括 L、lo、hi、best、val 五个字段。val 必须用 int64因为前缀和的累加和最终答案都可能超过 int32。3.2 ST 表预处理细节ST 表里每一层存的是下标而不是值。这一点很重要。因为最终我们要拿到 best 的具体位置才能分裂区间。如果只存最大值本身分裂时还得重新二分找位置非常麻烦。构建 ST 表的 Go 代码如下pre : make([]int64, n1) for i : 0; i n; i { pre[i1] pre[i] int64(nums[i]) } m : n 1 logv : make([]int, m1) for i : 2; i m; i { logv[i] logv[i/2] 1 } K : logv[m] 1 st : make([][]int, K) st[0] make([]int, m) for i : 0; i m; i { st[0][i] i } for j : 1; j K; j { half : 1 (j - 1) st[j] make([]int, m-(1j)1) for i : 0; i(1j) m; i { a : st[j-1][i] b : st[j-1][ihalf] if pre[a] pre[b] { st[j][i] a } else { st[j][i] b } } }查询函数如下query : func(l, r int) int { if l r { return -1 } j : logv[r-l1] a : st[j][l] b : st[j][r-(1j)1] if pre[a] pre[b] { return a } return b }需要特别注意的是当 pre 出现相等的情况时取左边还是右边不影响最终结果因为另一个相等值会在分裂后被重新入堆。但我建议统一用保持行为一致。3.3 堆节点的设计与大根堆实现Go 的container/heap默认是最小堆要让 val 大的先弹出Less里就要写成“我大于你”。代码是这样的type Item struct { L int lo int hi int best int val int64 } type MaxHeap []*Item func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { if h[i].val ! h[j].val { return h[i].val h[j].val } if h[i].L ! h[j].L { return h[i].L h[j].L } return h[i].best h[j].best } func (h MaxHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MaxHeap) Push(x interface{}) { *h append(*h, x.(*Item)) } func (h *MaxHeap) Pop() interface{} { old : *h n : len(old) item : old[n-1] *h old[:n-1] return item }这里加了一个简单的 tie-breaker当 val 相同时按 L 和 best 排序。这主要是为了让行为稳定对答案没有影响。3.4 主流程初始化、循环 k 次、答案累加初始化时每个左端点 L 的右端点范围是 [L1, n]查一下 ST 表得到 best算好 val全部入堆。然后连续弹 k 次每次弹出后分裂成左右两个候选区间。主函数实现如下func maxKSubarraySum(nums []int, k int) int64 { n : len(nums) if n 0 || k 0 { return 0 } total : n * (n 1) / 2 if k total { // 实际题目通常保证 k total // 这里简单返回 0正式场景应按题意做错误处理 return 0 } // 构建前缀和 pre : make([]int64, n1) for i : 0; i n; i { pre[i1] pre[i] int64(nums[i]) } // 构建 ST 表 m : n 1 logv : make([]int, m1) for i : 2; i m; i { logv[i] logv[i/2] 1 } K : logv[m] 1 st : make([][]int, K) st[0] make([]int, m) for i : 0; i m; i { st[0][i] i } for j : 1; j K; j { half : 1 (j - 1) st[j] make([]int, m-(1j)1) for i : 0; i(1j) m; i { a : st[j-1][i] b : st[j-1][ihalf] if pre[a] pre[b] { st[j][i] a } else { st[j][i] b } } } query : func(l, r int) int { if l r { return -1 } j : logv[r-l1] a : st[j][l] b : st[j][r-(1j)1] if pre[a] pre[b] { return a } return b } h : MaxHeap{} heap.Init(h) for L : 0; L n; L { lo, hi : L1, n best : query(lo, hi) val : pre[best] - pre[L] heap.Push(h, Item{L: L, lo: lo, hi: hi, best: best, val: val}) } var ans int64 0 for cnt : 0; cnt k; cnt { if h.Len() 0 { break } cur : heap.Pop(h).(*Item) ans cur.val L : cur.L lo, hi, best : cur.lo, cur.hi, cur.best if lo best-1 { b2 : query(lo, best-1) heap.Push(h, Item{ L: L, lo: lo, hi: best - 1, best: b2, val: pre[b2] - pre[L], }) } if best1 hi { b2 : query(best1, hi) heap.Push(h, Item{ L: L, lo: best 1, hi: hi, best: b2, val: pre[b2] - pre[L], }) } } return ans }在主函数里用一个简单例子调用验证func main() { nums : []int{10, 9, 8, 7, 6} k : 2 fmt.Println(maxKSubarraySum(nums, k)) // 输出 74 }这个输出正好印证了前面说的结果允许重叠时选 [0,4] 和 [0,3]总和是 74。4. 复杂度分析与其他解法的取舍4.1 时间复杂度与空间复杂度整个算法分三段前缀和计算O(n)ST 表预处理O(n log n)初始化堆每个左端点入堆一次O(n log n)循环 k 次每次弹出堆顶 O(log n)分裂后最多入堆两个新节点也是 O(log n)总 O(k log n)。所以整体复杂度是 O((n k) log n)空间复杂度 O(n log n)。在 n 和 k 都是 2e5 的数据量下这个复杂度是可以轻松跑完的。对比一下如果直接枚举所有区间然后排序区间数是 n(n1)/2n2e5 时大约是 2e10 个区间根本不可能。如果只枚举 k 个但每次用固定左端点找最大也无法处理“每个左端点需要多个右端点”的情况。所以这个“ST 表 堆 区间分裂”的方案在思路上几乎是必然的选择。4.2 为什么不能直接套 Kadane 或普通贪心Kadane 解决的是“只选一个区间”的问题。如果你把它强行扩展成“选 k 个区间”常见的做法是每次选最大子数组然后把这段取反再继续选。这个技巧只对“选中区间后不再重复使用”的模型有效。但本题允许重叠选中 [0,4] 后[0,3] 依然可以贡献 34 的额外收益。取反会导致 [0,3] 的收益变成 -34 或类似值完全错误。普通贪心的问题更明显。如果每次选全局最大然后从数组中删掉这个区间再找下一段这会强制后续区间避开已选区域。可现在后选的区间可以完全包含在已选区里也可以和已选区交错这种“删除”操作会把大量合法的次优方案给丢掉。前文 [10, 9, 8, 7, 6] 的例子已经充分说明了这一点。4.3 为什么 DP 在这种规则下也很麻烦如果你设 dp[i][j] 为前 i 个元素中选 j 个区间的最大和转移的时候通常会枚举最后一个区间的左端点看起来是 O(n^2 k)。更大的问题在于去重允许重叠且区间互不相同dp 的前 j-1 个区间里可能已经包含了你想作为第 j 个加入的那个区间你又不能简单地把这种方案排除掉因为你不知道是否还有另一种不含重复区间的组合更优。要准确处理就需要在状态里带上“最后选了哪些右端点”之类的信息这是指数级的。因此对于这道题DP 不是不能做而是很难在竞赛级数据范围内做到既正确又高效。Top-K 框架绕开了这个麻烦因为它不需要构造“状态”只需要一个强有力的“取最大候选人”机制。4.4 和超级钢琴题目的关联如果你接触过“超级钢琴”会发现这个代码结构非常眼熟。超级钢琴要求子区间长度在某个范围内求前 k 大的区间和解法就是对每个左端点维护右端点候选区间用 RMQ 找到最大 pre然后分裂入堆。这道题其实就是超级钢琴的无长度限制版。限制更少反而让人容易往复杂的方向想。以后遇到“从所有子数组里取前 k 大”或者“选 k 个结构不同的区间最大化总和”这类题可以第一时间想到这个框架。5. 实测与边界条件5.1 手写几个用例验证我用几个典型用例跑过这里记录一下结果。第一个是全是正数的数组[5, 5, 5]k2。所有子数组和按从大到小是 15、10、10、5、5、5前两个加起来是 25。跑出来的结果就是 25。第二个是带负数的数组[5, -3, 4]k2。所有子数组和是 6、5、4、2、1、-3前两个是 6 和 5答案 11。代码输出 11。第三个是[-1, 10]k2。区间和是 10、9、-1前两个是 10 和 9答案 19。代码输出 19。这几个用例覆盖了正数段、负数段、单元素区间都能得到正确结果。5.2 容易踩的坑我实际写代码时踩了几个坑这里列一下。第一个坑是整数溢出。前缀和、区间和、答案都要用 int64尤其当 n 到 2e5、nums 元素也很大时int32 很容易爆。Go 的 int 在 64 位系统上是 64 位但在 32 位机器上有风险所以最好明确用 int64。第二个坑是 k 大于总区间数。总区间数是 n*(n1)/2。如果 k 超过这个数理论上没有合法方案。竞赛题通常会保证 k 不超过这个上限但如果自己造数据要提前判断。我在代码里直接 return 0 只是占位实际场景应该返回一个错误或者按题意约定处理。第三个坑是 ST 表的边界。st[j]的切片长度不是 m而是 m-(1j)1。查询的时候r-(1j)1这个位置可能让新手困惑但只要保证lo到hi的范围是合法的就没问题。我把query写成闭包并且先判断l r这样能避免空区间导致越界。第四个坑是收集堆节点时Item里的lo和hi在下一次分裂前要原样保留。如果误改了当前节点的范围会导致后续分裂错乱。我用值拷贝的方式传递不会改原节点但如果你用指针复用就要小心。第五个坑是大量重复的 pre 值。比如全零数组所有区间和都是 0ST 表查询会稳定返回一个位置。功能上没有问题因为另一个候选位置会在分裂后重新入堆答案也不会多算或者漏算。5.3 扩展思考如果要求区间长度有上下限这个算法稍微改一下就能处理一个更常见的变体每个子数组的长度必须在 [a, b] 范围内求前 k 大区间和。做法是固定左端点 L 时右端点 R 的可选范围从 [L1, n] 变成 [La, Lb]同样查询区间内 pre 最大值然后分裂入堆。这个变化说明算法的本质不是依赖“区间无限制”这个条件而是依赖“对于一个左端点它的右端点候选是一个连续区间”。只要候选右端点可以用连续区间表示ST 表就能查最大值分裂逻辑也就成立。5.4 如果题目改成“恰好 k 个互不重叠区间”怎么办这个变体是 Codeforces 280D 那类题做法是线段树维护最大子段和每选一段后把这段取反通过“可撤销贪心”来支持多次选择。思路完全不同因为不重叠要求你在选中一个区间后把它从可选区域中“切除”而允许重叠时“切除”会误伤合法的重叠候选。面试和刷题时区分清楚题目到底允不允许重叠基本决定了你会走哪条路线。遇到“允许重叠、但区间不能完全相同”优先想 Top-K 子区间和遇到“不重叠”优先想动态规划、费用流、或者贪心 取反。我自己在实际做题中最深的体会是这道题最反直觉的地方不是堆也不是 ST 表而是“允许重叠”这个条件会直接把人的思维钉死在区间互斥的旧模型里。一旦想明白它本质上是“从一堆数值里取前 k 大”整个题目一下子就变得非常清晰了。把 (L, R) 唯一映射到子区间用前缀和把区间和变成两个 pre 值的差再用 RMQ 支持候选查询最后用堆保证全局有序这套组合拳以后遇到类似的题都可以直接套。