本文介绍一种针对特定构造序列 `b` 的最大值求解方法，该序列由数组 `a` 递推生成；通过挖掘前缀和与滚动更新的数学结构，将暴力 o(n²) 解法优化至最优的 o(n) 时间、o(1) 空间复杂度。
该问题的核心在于理解序列 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 实际按“轮次”（round）组织：第 i 轮（从 0 开始）生成 i+1 个新元素，且每轮均以某个基础值 b_start 为起点，依次累加 a[0], a[0]+a[1], ..., a[0]+...+a[i]。即：
- 第 0 轮：b[0] = 0（仅起始）
- 第 1 轮（i=0）：b[1] = b[0] + a[0]
- 第 2 轮（i=1）：b[2] = b[1] + a[0], b[3] = b[2] + a[1] = b[1] + a[0] + a[1]
- 第 3 轮（i=2）：b[4] = b[3] + a[0], b[5] = b[4] + a[1], b[6] = b[5] + a[2]
→ 每轮 i 对应对 a[0..i] 的所有前缀和进行累加。
因此，第 i 轮中 b 的最大值为：
b_start_i + max_prefix_sum(a[0..i]),
其中 b_start_i 是该轮首个 b 值（即上一轮最后一个 b 值），而 max_prefix_sum(a[0..i]) 是 a 前 i+1 项的前缀和最大值。
关键洞察：我们无需显式构建整个 b 数组，只需在遍历 a 过程中维护两个变量：
- b: 当前轮次的起始 b 值（即上一轮末尾值）；
- sum_a: 当前已处理 a 的累计和（即 a[0..i] 总和）；
- max_sum_a: a[0..i] 的最大前缀和（动态更新）；
- max_b: 全局 b 序列历史最大值。
每处理一个 a[i]，即可完成一轮更新：
- 将 a[i] 加入 sum_a；
- 更新 max_sum_a = max(max_sum_a, sum_a)；
- 本轮 b 的最大值为 b + max_sum_a，用其更新 max_b；
- 更新 b += sum_a，作为下一轮的起始值。
最终代码简洁高效：
def find_max_linear(a):
b = max_b = 0 # 当前轮起始b值，全局最大b值
sum_a = max_sum_a = 0 # 当前a前缀和，当前最大前缀和
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) —— 仅使用常数额外变量；
⚠️ 注意：初始 max_b = 0 已涵盖 b[0] = 0，即使所有 a[i] 为负，结果也不会遗漏零点。
进阶技巧：利用 itertools.accumulate 可写出函数式风格的一行解（O(n) 时间，O(n) 空间）：
from itertools import accumulate
from operator import add
def find_max_linear_oneliner(a):
acc_a = list(accumulate(a)) # [a0, a0+a1, a0+a1+a2, ...]
prefix_sums = list(accumulate(acc_a, max)) # max prefix sums up to each i
b_starts = [0] + list(accumulate(acc_a)) # b[0], b[1], b[3], b[6], ... (start of each round)
return max(0, *map(add, b_starts, prefix_sums))该算法不仅显著优于朴素 O(n²) 暴力法，更体现了“识别结构 → 抽象状态 → 滚动更新”的典型优化思维。适用于在线计算、内存受限或大规模数据场景。
