企业官网建设流程全解析

最近看到一道很有意思的题，名字叫“最大子数组总值Ⅱ”。乍一看以为是经典的最大子数组和，但读完题目才发现它玩的是另一种花样：给定整数数组 nums 和一个整数 k，要从数组里挑出恰好 k 个互不相同的非空连续子数组，允许这些子数组相互重叠，但不允许重复选同一对左右端点，最后让这 k 个子数组的和加起来最大。这道题用 Go 语言来解，本质上是个“所有子数组和中取前 k 大”的问题，解法很有代表性。

如果你已经有 Go 语言环境，直接go run就能把后面的代码跑起来。这篇文章我从题意拆解讲到高效算法，再给出完整的 Go 实现和踩坑记录，适合想练算法、准备面试，或者单纯想知道“为什么区间可以重叠反而是个好消息”的人。

1. 题目到底在问什么

1.1 一句话翻译

原题描述里的关键词是：“恰好 k 个”、“互不相同”、“非空连续区间”、“允许重叠但不能重复选取同一对左右端点”。

把它翻译成更直白的话：数组里有n(n+1)/2个非空连续子数组，每个子数组都有自己的和。我们要从这些候选中挑 k 个，使它们的和加起来最大。唯一限制是每个子数组“只能用一次”，这里的“一次”指的是左右端点组合不能重复，而不是位置不能重叠。

举个例子，数组[1, 3, -2]的子数组有：

• [1]和是 1
• [3]和是 3
• [-2]和是 -2
• [1,3]和是 4
• [3,-2]和是 1
• [1,3,-2]和是 2

如果 k=3，那挑和最大的三个：[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[r+1] - pre[l]

其中l <= r。如果令i = l，j = r+1，那么条件就变成0 <= i < j <= n。

所以原问题完全等价于：从所有满足i < j的差值pre[j] - pre[i]中，找出最大的 k 个，并把它们加起来。这种转换最大的好处是：子数组的枚举被压缩成了前缀和两两之间的差值，数量仍然是 n(n+1)/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：

1. 计算limit = pre[j] - x；
2. 在离散化数组里二分找到最后一个<= limit的 rank；
3. 在两棵树里查询前缀[1, rank]，拿到cnt和sumPre；
4. 把cnt * pre[j] - sumPre累加到“总差值”里去；
5. 把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结构体。它内部维护两个长度是n+1的 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 }) - 1

4.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，而我们只需要其中一部分。

处理方法分两步：

1. 用calc(val + 1)拿到“严格大于 val”的个数upperCnt和总和upperSum；
2. 还需要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, n+1), sum: make([]int64, n+1)} } 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[i+1] = 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 lo+1 < 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 实现不算短，但每个模块都很清晰：前缀和、离散化、树状数组、二分答案。只要把“区间和等于前缀和之差”这层窗户纸捅破，后面就是标准操作了。