本文介绍一种 o(n) 时间、o(1) 空间的高效算法，用于求解由数组 `a` 构造的特殊序列 `b` 中的最大值，避免暴力 o(n²) 方法，核心在于动态维护前缀和极值与累积基准值。
该问题的关键在于理解序列 b 的构造规律。观察给出的生成过程：
b[0] = 0 b[1] = b[0] + a[0] b[2] = b[1] + a[0] b[3] = b[2] + a[1] b[4] = b[3] + a[0] b[5] = b[4] + a[1] b[6] = b[5] + a[2] b[7] = b[6] + a[0] ...
可发现：b 被自然划分为若干“轮次（rounds）”，第 i 轮（从 0 开始）共产生 i+1 个新元素，且每轮的增量严格取自 a[0..i] 的前缀——更准确地说，第 i 轮（对应 a[i] 首次参与）的所有新增 b 值，均以某一个“起始 b 值”为基底，依次加上 a[0]、a[0]+a[1]、a[0]+a[1]+a[2]、…、sum(a[0..i])。
例如第 2 轮（i=2，生成 b[4]~b[6]）：
- 起始值为 b[3]
- 后续为 b[3] + a[0]、b[3] + a[0]+a[1]、b[3] + a[0]+a[1]+a[2]
因此，该轮中 b 的最大值 = b[3] + max_prefix_sum(a[0..2])。而下一轮的起始 b 值即为本轮末尾值 b[6] = b[3] + sum(a[0..2])。
由此提炼出两个需动态维护的核心变量：
- b：当前轮次的起始 b 值（初始为 0）
- sum_a：当前轮对应 a 前缀的累加和（即 sum(a[0..i])）
- max_sum_a：当前轮对应前缀中最大前缀和（即 max(sum(a[0..0]), sum(a[0..1]), ..., sum(a[0..i]))）
- max_b：全局至今遇到的最大 b 值（初始为 0，因 b[0]=0）
每遍历 a[i]，我们：
- 更新 sum_a += a[i]
- 更新 max_sum_a = max(max_sum_a, sum_a)
- 本轮最大 b 为 b + max_sum_a，用其更新 max_b
- 更新 b += sum_a，为下一轮准备起始值
最终 max_b 即为答案。
以下是简洁、健壮的 Python 实现：
def find_max_linear(a):
b = max_b = 0 # 当前轮起始b值，全局最大b值
sum_a = max_sum_a = 0 # 当前前缀和，当前前缀中最大前缀和
for x in a:
sum_a += x
max_sum_a = max(max_sum_a, sum_a)
max_b = max(max_b, b + max_sum_a)
b += sum_a
return max_b✅ 时间复杂度：O(n)，单次遍历 a
✅ 空间复杂度：O(1)，仅使用常数额外变量
⚠️ 注意：算法天然包含 b[0] = 0，故即使所有 b[i]
作为验证，该实现已通过大量随机测试（含负数、零、正数混合），结果与朴素 O(n²) 方法完全一致。对于大规模输入（如 n=10⁵），线性解法具备显著性能优势。
