本文介绍一种 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 是按“轮次（round）”分组生成的——第 i 轮（从 0 开始）新增 i+1 个元素，且这些元素均以第 i 轮起始的 b 值为基础，依次累加 a[0], a[0]+a[1], a[0]+a[1]+a[2], …, sum(a[0..i])。换言之，第 i 轮生成的子序列等价于：
b_start_i + prefix_sum(a[0..0]), b_start_i + prefix_sum(a[0..1]), ..., b_start_i + prefix_sum(a[0..i])
因此，该轮内 b 的最大值 = b_start_i + max_prefix_sum(a[0..i])。
关键洞察在于：我们无需显式构建整个 b 数组，只需在遍历 a 的过程中动态维护两个核心量：
- b 当前轮次的起始值（即上一轮末尾的 b 值）；
- a 前缀和序列中的当前最大值（即 max(prefix_sum(a[0..i]))）。
而这两者均可在 O(1) 时间内递推更新：
- 设 sum_a 表示 a[0..i] 的和（即当前轮次完整前缀和），则 b 的下一轮起始值就是 b += sum_a；
- max_sum_a = max(max_sum_a, sum_a) 即为当前最大前缀和；
- 本轮 b 的最大候选值为 b_prev_round_start + max_sum_a，与全局最大值 max_b 比较更新。
由此得到简洁高效的线性解法：
def find_max_linear(a):
b = max_b = 0 # b: 当前轮起始值；max_b: 全局最大b值
sum_a = max_sum_a = 0 # sum_a: a[0..i]之和；max_sum_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 = 起始b + 最大前缀和
b += sum_a # 更新下一轮起始b值
return max_b✅ 时间复杂度：O(n) —— 单次遍历 a；
✅ 空间复杂度：O(1) —— 仅使用常数额外变量；
⚠️ 注意事项：
- 初始 b[0] = 0 已包含在 max_b = 0 初始化中，无需额外处理；
- a 可含负数或零，算法天然支持（因 max_sum_a 可能保持为 0，对应不取任何前缀）；
- 若所有前缀和均为负，max_sum_a 将维持为 0，此时 max_b 至少为 0（即 b[0]），符合定义。
作为补充，还可借助 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, ...]
acc_acc_a = list(accumulate(acc_a)) # 各轮起始b值（不含b[0]）
max_prefix = list(accumulate(acc_a, max)) # 各轮最大前缀和
return max(0, *map(add, [0] + acc_acc_a, [0] + max_prefix))但生产环境推荐首选第一版——它无额外空间开销、逻辑清晰、易于验证与调试。该解法不仅解决了本题，更体现了“识别结构 → 抽象状态 → 动态递推”的典型算法优化思维。
