• 科学计算

导读

本文基于 leetcode/biweekly/102/b/README.md 中记录的双周赛 102 第二题解法，完整讲解「Find the Score of All Prefixes of an Array（数组所有前缀的得分）」的题目定义、单遍扫描思路与多语言实现，并结合 codeforces-go 仓库中对应的 b.go 实现与 b_test.go 测试工程，深入展示该题在算法竞赛模板库中的落地方式。读完本文，你将掌握一类"维护前缀最大值 + 前缀累计"的经典线性扫描技巧，以及该仓库如何用数据文件驱动 + 随机对拍的方式为单函数题做验证。

问题定义：什么是"数组所有前缀的得分"

题目要求对给定整数数组nums的每个前缀计算得分，并返回得分数组。得分规则如下（依据仓库 README 及实现）：

• 对下标i，取前缀nums[0..i]中的最大值mx[i] = max(nums[0..i])；
• 每个位置j的"单点得分"定义为nums[j] + mx[j]，即当前元素加上到它为止的前缀最大值；
• 前缀i的得分score[i]是0..i所有单点得分之和。

换句话说，答案数组的第i项是一个嵌套累加：

score[i] = Σ (nums[j] + max(nums[0..j])) (j = 0..i)

以仓库中 b.txt 的第一组测试数据为例：

nums = [2, 3, 7, 5, 10] 答案 = [4, 10, 24, 36, 56]

逐步推演验证定义：

这正是原文档中"一边遍历，一边计算前缀最大值 mx，以及前缀的得分之和 s"的核心脉络。

核心思路：单遍扫描维护两个滚动变量

若对每个前缀都重新扫描求最大值，总复杂度会退化为 O(n²)。本题的关键洞察在于：

1. 前缀最大值具有单调性：mx = max(mx, x)只需一次比较即可由上一个前缀的最大值递推而来，且单调不减；
2. 前缀得分具有累计性：score[i] = score[i-1] + (nums[i] + mx[i])，后一个前缀的得分可以从前一个前缀的得分直接递推。

因此只需维护两个变量：

• mx：当前遍历到的前缀最大值；
• s：当前遍历到的前缀得分累计和。

每读到一个元素x，先更新mx = max(mx, x)，再执行s += x + mx，把s写入答案数组对应位置。整个过程中每个元素只被处理一次，全程只用两个额外变量。

Python 实现（继承自原文档）

class Solution: def findPrefixScore(self, nums: List[int]) -> List[int]: ans = [] mx = s = 0 for x in nums: mx = max(mx, x) # 前缀最大值 s += x + mx # 累加前缀的得分 ans.append(s) return ans

Go 实现（继承自原文档）

func findPrefixScore(nums []int) []int64 { ans := make([]int64, len(nums)) mx, s := 0, 0 for i, x := range nums { mx = max(mx, x) // 前缀最大值 s += x + mx // 累加前缀的得分 ans[i] = int64(s) } return ans } func max(a, b int) int { if a < b { return b }; return a }

两处实现需要注意的工程细节：

• 返回值类型为[]int64而非[]int：由于得分随前缀不断累加，n 较大时可能超出 32 位整数范围，因此仓库中的 Go 解法在写入答案时显式做int64(s)转换（见 b.go 第 10 行），这与题目给出的返回值签名保持一致。
• max需要自行定义：LeetCode Go 环境中早期版本的内置max并不总可用，仓库实现里显式给出了func max(a, b int) int的手写版本，保证模板可独立复制运行。

复杂度分析

• 时间复杂度：O(n)，其中 n 为nums的长度。每个元素仅进入循环一次，循环体内的比较与加法均为常数操作，不存在任何嵌套扫描。
• 空间复杂度：O(1)（返回值数组不计入）。除答案数组外，仅使用mx、s与循环变量等常数个额外变量，符合原文档中的结论。

对于前缀类问题的滚动递推，这已经是最优的线性复杂度：至少要读取全部 n 个元素才能计算出每个前缀的得分。

仓库中的工程实践：实现、数据驱动测试与随机对拍

本题在该仓库中不是孤立的题解笔记，而是一套完整可运行的工程样例，四件套文件位于 leetcode/biweekly/102/b/：

1. 可独立运行的 Go 实现 b.go

仓库实现与原文档中的 Go 代码完全一致，包名为main，函数签名findPrefixScore(nums []int) []int64，并在文件头保留出处注释。该实现可以直接放入 LeetCode 的 Go 提交框使用。

2. 数据驱动的测试文件 b_test.go

测试文件由copypasta/template/leetcode/generator_test.go生成，包含两层验证：

func Test_b(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, findPrefixScore, "b.txt", targetCaseNum); err != nil { t.Fatal(err) } if err := testutil.RunFuncWithRandomInput(t, findPrefixScore); err != nil { t.Fatal(err) } }

• 第一层：官方样例验证。testutil.RunLeetCodeFuncWithFile读取 b.txt，逐行解析输入与期望输出并逐一断言。其底层实现在 leetcode/testutil/leetcode.go：先过滤空行，再按fNumIn + fNumOut（即"入参行数 + 返回值行数"）为一组切分测试数据，最后交给RunLeetCodeFuncWithExamples通过反射调用被测函数、比对输出。targetCaseNum的语义为：0表示跑全部用例并启用超时检测，-1表示只跑最后一组用例。
• 第二层：无尽随机对拍。testutil.RunFuncWithRandomInput会不断用随机生成的输入调用findPrefixScore，与参考实现比对结果，用于在官方样例之外验证算法的鲁棒性。这一机制对应 leetcode.go 中的CompareInf无尽对拍模式：默认MaxTestCase = math.MaxInt，并利用 2 秒的DebugTLE超时窗口（定义于 leetcode/testutil/config.go）自动标记可能超时的用例。

3. 官样例文件 b.txt

文件按"输入行 + 输出行"成对组织，空行会被测试框架自动忽略。仓库中共存两组用例：

[2,3,7,5,10] [4,10,24,36,56] [1,1,2,4,8,16] [2,4,8,16,32,64]

第二组用例恰好展示了数组元素本身构成前缀最大值链（每个元素都大于等于前缀中所有元素）的边界形态：此时单点得分恒为2*x，累计得分呈 2、4、8、16、32、64 的倍增序列。

运行方式

在仓库根目录执行以下命令即可复现测试结果：

go test ./leetcode/biweekly/102/b/ -v

该测试依赖testutil包，测试数据文件路径b.txt以相对路径传入，因此命令必须从仓库根目录发起。运行成功时，go test会输出两组用例均通过的结论。

总结：一类可推广的"前缀递推"技巧

本题的算法本质是把"求前缀统计量"从朴素的两层循环优化为单遍滚动：

• 凡是统计量可以由前缀统计量 + 当前元素递推（前缀最大值、前缀和、前缀最值差、前缀相等段等）的问题，都可以考虑这种 O(n) 的单遍扫描；
• 维护的滚动变量数量通常等于递推关系中的状态数——本题恰好是两个（mx与s），二者更新顺序固定：先更新前缀最大值，再更新依赖它的累计得分。

结合仓库 leetcode/biweekly/102/b/ 下的实现与测试四件套，读者既可以把它当作一份可直接复制提交的 LeetCode 题解，也可以作为学习 codeforces-go 仓库"函数题数据驱动测试 + 随机对拍"工程范式的最小样例。

• 科学计算