最近看到一道很有意思的题名字叫“最大子数组总值Ⅱ”。乍一看以为是经典的最大子数组和但读完题目才发现它玩的是另一种花样给定整数数组 nums 和一个整数 k要从数组里挑出恰好 k 个互不相同的非空连续子数组允许这些子数组相互重叠但不允许重复选同一对左右端点最后让这 k 个子数组的和加起来最大。这道题用 Go 语言来解本质上是个“所有子数组和中取前 k 大”的问题解法很有代表性。如果你已经有 Go 语言环境直接go run就能把后面的代码跑起来。这篇文章我从题意拆解讲到高效算法再给出完整的 Go 实现和踩坑记录适合想练算法、准备面试或者单纯想知道“为什么区间可以重叠反而是个好消息”的人。1. 题目到底在问什么1.1 一句话翻译原题描述里的关键词是“恰好 k 个”、“互不相同”、“非空连续区间”、“允许重叠但不能重复选取同一对左右端点”。把它翻译成更直白的话数组里有n(n1)/2个非空连续子数组每个子数组都有自己的和。我们要从这些候选中挑 k 个使它们的和加起来最大。唯一限制是每个子数组“只能用一次”这里的“一次”指的是左右端点组合不能重复而不是位置不能重叠。举个例子数组[1, 3, -2]的子数组有[1]和是 1[3]和是 3[-2]和是 -2[1,3]和是 4[3,-2]和是 1[1,3,-2]和是 2如果 k3那挑和最大的三个[1,3]和 4[3]和 3[1,3,-2]和 2总和是 9。这里[1]和[3,-2]虽然都是 1但如果 k 只需要 3 个就不需要考虑它们。1.2 和经典最大子数组和的差异最经典的最大子数组和是“找一段连续区间让和最大”通常用 Kadane 算法 O(n) 解决。而这道题叫“Ⅱ”说明难度上了一个台阶它要求的不再是一段而是 k 段。但要注意它和另一类“ k 个最大子数组和”也不一样。很多题目里会加“这些子数组不能重叠”那样就成了选 k 段互不相交的最大和得用 DP 或者费用流之类的技巧。这道题明确说“允许重叠”所以每个子数组和跟其他子数组没有耦合关系。换句话说问题退化成了一个独立的 Top K 问题把所有子数组和排个序取前 k 大相加。“允许重叠”反而让问题变简单了这一点特别反直觉。重叠如果不限制那么同一个元素可以同时贡献给多个区间区间之间的约束就消失了。真正要解决的问题只剩一个怎么快速找出所有子数组和里的前 k 大。1.3 数据范围决定解法如果 n 很小比如 n ≤ 2000暴力枚举所有子数组和排序取前 k 个完全可行。因为总共也就是 200 万个区间Go 排序非常快。但这类题目通常没那么善良。n 一旦到 10^5总区间数就是 5×10^9内存和时间都不可能让你枚举完整。就算只找前 k 大k 也可能非常大比如 k min(总区间数的一半)。这时候不能用堆滑窗之类的简单技巧必须在一个更加数学化的层面思考。后面要讲的解法是二分答案 树状数组Fenwick Tree。它能做到 O(n log n log V) 的时间复杂度V 是前缀和值域即使 n 是 10^5 级别也能跑完。2. 为什么可以转化为“所有区间和 Top K”2.1 区间和 前缀和之差处理区间和问题第一个条件反射应该是前缀和。定义前缀和数组pre[i]表示nums[0..i-1]的和pre[0] 0 pre[i] pre[i-1] nums[i-1] // i 1那么任意子数组nums[l..r]的和等于pre[r1] - pre[l]其中l r。如果令i lj r1那么条件就变成0 i j n。所以原问题完全等价于从所有满足i j的差值pre[j] - pre[i]中找出最大的 k 个并把它们加起来。这种转换最大的好处是子数组的枚举被压缩成了前缀和两两之间的差值数量仍然是 n(n1)/2但公式非常干净。2.2 把“原数组”变成“前缀和数组”这一步是核心思维跳跃后面所有操作都在pre上进行没有再回头看过nums。为什么这个转换有助于解决 Top K 问题因为pre[j] - pre[i]是否大于等于某个阈值x可以被改写成pre[j] pre[i] x也就是说如果我们固定j想知道有多少个i j满足条件本质上是在问在pre[0..j-1]中有多少个数的值小于等于pre[j] - x。这是一个“左边历史值”的查询。对于这种问题树状数组、线段树、平衡树都能胜任。因为我们要统计的是满足条件的数量还要顺便统计这些pre[i]的和所以用两个树状数组最方便。2.3 暴力做法能走多远我一开始写了个暴力验证版本func brute(nums []int, k int) int64 { var sums []int64 for i : 0; i len(nums); i { s : int64(0) for j : i; j len(nums); j { s int64(nums[j]) sums append(sums, s) } } sort.Slice(sums, func(i, j int) bool { return sums[i] sums[j] }) var ans int64 for i : 0; i k; i { ans sums[i] } return ans }这个代码能在 n 小的时候对拍但 n 10^5 时会直接内存爆炸。我建议你写算法前先把暴力版准备好后面拿它和小数据随机用例对拍这种习惯能少掉很多头发。3. Top K 区间和的高效解法3.1 二分答案猜第 K 大的值在所有差值里面找第 k 大最常见的思路是二分答案。设一个阈值x定义count(x) 有多少对(i, j)满足i j且pre[j] - pre[i] x。这个函数是关于x单调递减的x越大符合条件的差值越少x越小符合条件的差值越多。如果count(x) k说明第 k 大的值至少是x可以尝试更大的x如果count(x) k说明第 k 大的值小于x需要把x调小。最终二分出来的那个最大的x就是第 k 大的差值。二分上下界不需要太精确。由于前缀和的最小值和最大值是确定的所有差值的上界不会超过maxPre - minPre下界不会小于minPre - maxPre。用这两个当作二分边界二分次数大约是log2(2 * maxAbs * n)最多六十多次完全可以接受。3.2 统计函数 calc(x) 的核心公式关键在于count(x)和“所有满足条件的差值总和”怎么一并算出来。固定j时所有满足条件的i j都满足pre[i] pre[j] - x这个差值总和可以写成sum( pre[j] - pre[i] ) cnt * pre[j] - sum(pre[i])其中cnt是满足条件的i的数量sum(pre[i])是这些pre[i]的和。于是问题又变成了从左到右扫描pre在碰到新的j之前把自己左边的所有pre值都维护在一个数据结构里然后查询“值小于等于某个上限”的个数和和值。这就是经典的“二维偏序”或者“前缀查询”用树状数组完全可以做。3.3 用两个树状数组维护数量与总和树状数组本身维护的是一个下标序列的前缀信息。但pre[i]是数值不是下标所以需要先离散化把所有可能的pre值排序去重然后每个pre对应一个从 1 开始的 rank。我们要维护两棵树第一棵树记录某个 rank 对应的pre[i]出现了几个第二棵树记录某个 rank 对应的pre[i]的累加和。在扫描j之前先插入pre[0]。然后对于每个j 1..n计算limit pre[j] - x在离散化数组里二分找到最后一个 limit的 rank在两棵树里查询前缀[1, rank]拿到cnt和sumPre把cnt * pre[j] - sumPre累加到“总差值”里去把pre[j]插入两棵树供后面的j使用。整个过程保证i j不会重复也不会遗漏。3.4 二分边界怎么写边界处理是这道题最容易出错的地方。我采用“左闭右开”的写法lo初始化为所有差值都一定满足的下界hi初始化为所有差值都不一定满足的上界循环条件用lo 1 hi如果mid时count(mid) k说明mid可行lo mid否则hi mid。这样退出循环时lo就是最大的可行值也就是第 k 大差值本身。需要注意一点这里count(mid)计算的是“差值大于等于 mid 的数量”不是“大于 mid”的数量。二分判断的是“第 k 大是否 mid”所以用完全正确。4. Go 语言实现细节4.1 离散化前缀和Go 标准库没有内置树状数组所以我们需要自己写一个BIT结构体。它内部维护两个长度是n1的 slice一个记数量一个记和值。在初始化pre之后把所有pre复制到一个[]int64排序去重。然后写一个rank函数rank : func(x int64) int { return sort.Search(len(uniq), func(i int) bool { return uniq[i] x }) 1 }注意这个rank只用于插入pre。查询的时候要找的是“最后一个小于等于 limit 的位置”所以单独用另一个二分idx : sort.Search(len(uniq), func(i int) bool { return uniq[i] limit }) - 14.2 完整的 calc 函数下面的代码是核心统计函数func (b *BIT) Reset() { for i : range b.cnt { b.cnt[i] 0 b.sum[i] 0 } } func (b *BIT) Add(pos int, val int64) { for i : pos; i b.n; i i -i { b.cnt[i] b.sum[i] val } } func (b *BIT) Query(pos int) (int64, int64) { var cnt, sum int64 for i : pos; i 0; i - i -i { cnt b.cnt[i] sum b.sum[i] } return cnt, sum }calc(x)闭包的实现calc : func(x int64) (int64, int64) { bit.Reset() bit.Add(rank(pre[0]), pre[0]) var totalCnt int64 var totalSum int64 for j : 1; j len(pre); j { limit : pre[j] - x idx : sort.Search(len(uniq), func(i int) bool { return uniq[i] limit }) - 1 if idx 0 { cnt, sumPre : bit.Query(idx 1) if cnt 0 { totalCnt cnt totalSum cnt*pre[j] - sumPre } } bit.Add(rank(pre[j]), pre[j]) } return totalCnt, totalSum }这里totalCnt就是count(x)totalSum是所有满足差值的总和。4.3 主流程与最终答案二分找到第 k 大的值val之后不能直接把calc(val)的和当成答案。因为可能有多个差值的值恰好等于val而我们只需要其中一部分。处理方法分两步用calc(val 1)拿到“严格大于 val”的个数upperCnt和总和upperSum还需要k - upperCnt个值等于val的差值所以最终答案ans : upperSum (int64(k)-upperCnt)*val这个公式很好理解所有大于第 k 大的都选上不够的数量用等于第 k 大的值补齐。4.4 完整代码下面是完整可运行的 Go 程序包含暴力对拍和 main 函数package main import ( fmt sort ) type BIT struct { n int cnt []int64 sum []int64 } func NewBIT(n int) *BIT { return BIT{n: n, cnt: make([]int64, n1), sum: make([]int64, n1)} } func (b *BIT) Reset() { for i : range b.cnt { b.cnt[i] 0 b.sum[i] 0 } } func (b *BIT) Add(pos int, val int64) { for i : pos; i b.n; i i -i { b.cnt[i] b.sum[i] val } } func (b *BIT) Query(pos int) (int64, int64) { var cnt, sum int64 for i : pos; i 0; i - i -i { cnt b.cnt[i] sum b.sum[i] } return cnt, sum } func maxSubarrayTotal(nums []int, k int) int64 { n : len(nums) m : n 1 pre : make([]int64, m) for i : 0; i n; i { pre[i1] pre[i] int64(nums[i]) } vals : make([]int64, m) copy(vals, pre) sort.Slice(vals, func(i, j int) bool { return vals[i] vals[j] }) uniq : vals[:0] for i : 0; i m; i { if i 0 || vals[i] ! vals[i-1] { uniq append(uniq, vals[i]) } } rank : func(x int64) int { return sort.Search(len(uniq), func(i int) bool { return uniq[i] x }) 1 } bit : NewBIT(len(uniq)) calc : func(x int64) (int64, int64) { bit.Reset() bit.Add(rank(pre[0]), pre[0]) var totalCnt int64 var totalSum int64 for j : 1; j m; j { limit : pre[j] - x idx : sort.Search(len(uniq), func(i int) bool { return uniq[i] limit }) - 1 if idx 0 { cnt, sumPre : bit.Query(idx 1) if cnt 0 { totalCnt cnt totalSum cnt*pre[j] - sumPre } } bit.Add(rank(pre[j]), pre[j]) } return totalCnt, totalSum } totalPairs : int64(m) * int64(m-1) / 2 if int64(k) totalPairs { return 0 } minPre, maxPre : pre[0], pre[0] for _, v : range pre[1:] { if v minPre { minPre v } if v maxPre { maxPre v } } lo : minPre - maxPre hi : maxPre - minPre 1 for lo1 hi { mid : lo (hi-lo)/2 cnt, _ : calc(mid) if cnt int64(k) { lo mid } else { hi mid } } val : lo upperCnt, upperSum : calc(val 1) ans : upperSum (int64(k)-upperCnt)*val return ans } func brute(nums []int, k int) int64 { var sums []int64 for i : 0; i len(nums); i { s : int64(0) for j : i; j len(nums); j { s int64(nums[j]) sums append(sums, s) } } sort.Slice(sums, func(i, j int) bool { return sums[i] sums[j] }) var ans int64 for i : 0; i k; i { ans sums[i] } return ans } func main() { nums : []int{1, 3, -2, 5, 2} k : 5 fmt.Println(fast:, maxSubarrayTotal(nums, k)) fmt.Println(brute:, brute(nums, k)) }我给main加了个小数据集跑出来的结果应该和暴力版一致。你可以把nums换成随机数组再多跑几个 k 对拍。5. 复杂度、边界与性能5.1 时间和空间复杂度一次calc(x)要扫描 n 个前缀和每个位置做一次树状数组查询和一次树状数组插入单次 O(log n)。二分大概执行 O(log V) 次V 是前缀和值域通常就是 60 次左右。所以总复杂度是O(n log n log V)空间上pre和离散化数组都是 O(n)两棵 BIT 也是 O(n)总空间 O(n)。这个复杂度对于 n 10^5 是非常舒服的Go 跑下来毫秒级。如果 n 到 10^6可能有点吃紧但仍然可优化比如用离线离散化加循环数组减少常数。5.2 边界情况到底有哪些我实际写的时候踩了几类边界数组元素全负数所有子数组和都是负的第 k 大也是负的。二分边界仍然有效但答案可能为负数别用 0 初始化答案。数组元素全零所有前缀和都一样离散化后只有一个值。此时limit也在同一个值上cnt累加正确总和始终为 0。k 等于总区间数此时答案应该是所有子数组和的总和。二分找最小差值upperCnt为 0最终是所有差值之和。这个用例特别适合检验calc的累加逻辑。k 等于 1本质上就是最大子数组和。可以用 Kadane 的结果来对拍。我在开发时写了一个随机对拍脚本在 n ≤ 30 的情况下把 fast 和 brute 的结果反复对比了几百组确认边界都没问题。5.3 溢出与内存小心点前缀和的值范围要开int64。如果 nums 元素本身可能是 int32但累加后可能超过 int32所以从nums[i]转成int64再算。calc里的limit : pre[j] - x也可能超出理论边界但用int64处理没问题除非值域超过 9e18。对于那些极端大数题目需要整体换big.Int但正常竞赛题不会这么恶心。内存方面最需要注意的是uniq切片去重的原地写法。我用vals[:0]复用了底层数组避免了再分配。如果你直接新建uniq数组也完全没问题只是在 n 很大时多一次 O(n) 分配。另一个小优化是BIT.Reset()不要重置n字段只清空两个切片。如果每次二分都NewBIT虽然逻辑也一样但会频繁触发 GC让常数变大。6. 编码过程中踩过的几个坑6.1 二分条件和 calc 统计方向别搞反一开始我把calc写成统计pre[j] - pre[i] x然后二分条件也跟着反过来了导致结果错得离谱。要始终记住calc(x)统计的是“大于等于 x”的数量。二分时如果数量够说明 x 太小要往右走数量不够说明 x 太大要往左走。虽然听起来简单但很容易顺手写反。6.2 树状数组清空不是直接 new我最早版本在calc里使用了同一个 BIT但没有调用 Reset结果第二次调用时树里保留了上一次的数据count 全部翻倍。发现问题后我给 BIT 加了一个 Reset 方法。如果你使用局部变量模拟要特别注意pre[0]在每次 calc 开始时都要重新插入。6.3 多个相同前缀和怎么算当 nums 中有很多负数或零时前缀和会出现大量重复值。离散化之后同一个 rank 会对应多个不同的下标但是它们的数值相同插入到树里都累加到同一个位置。查询的时候同一个pre[i]数值可能对应多个位置它们都会被统计进去这完全正确因为不同下标代表不同的子数组。有趣的是如果pre[i]和pre[j]相等那么差值 0 本身也会被计入。比如全零数组第 k 大全是 0此时calc(0)会给出所有区间数量calc(1)是 0所以最终答案永远是 0。6.4 重叠区间的理解误区很多人会误以为“允许重叠”又“不能重复选取同一对左右端点”是自相矛盾的。其实这里的意思是你可以同时选择nums[1..3]和nums[2..4]这两个区间有重叠元素但它们不是同一个区间。你唯一不能做的是把nums[1..3]选两次。在我们的算法中每一个(i, j)唯一对应一个区间天然不存在“同一个区间选两次”的问题所以不需要额外去重。这也就是为什么题目一旦允许重叠解法会从 DP 变成 Top K。如果它还要求区间互不重叠那就完全是另一道题了。最后再分享一个小技巧写这种基于二分的统计题建议把calc设计成同时返回数量和总和而不是分别写两个函数。因为最终答案必须同时用到这两个值你分开写会导致同样的扫描逻辑被重复执行两遍浪费时间不说还容易漏改。我实际在调试时就是靠这个双返回值省了大量时间。这道题的 Go 实现不算短但每个模块都很清晰前缀和、离散化、树状数组、二分答案。只要把“区间和等于前缀和之差”这层窗户纸捅破后面就是标准操作了。