特定结构序列b的最大值求解：是否存在优于O(n²)的算法？

给定长度为n的数组a，按如下规则构造序列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[8] = b[7] + a[1]
b[9] = b[8] + a[2]
b[10] = b[9] + a[3]
...

数组a可包含非正值，需找出序列b的最大值。现有O(n²)复杂度的解法，询问是否存在更高效的实现方式。

原O(n²)代码：

def find_max(a):
  b = [0]
  i = 0
  count = 0
  while i < len(a):
    j = 0
    while j <= i:
      b.append(b[count] + a[j])
      count += 1
      j += 1
    i += 1
  return max(b)

思路分析 #

通过观察序列b的构造规律，可以简化计算逻辑：

1. 序列b的元素（除b[0]外）可按组划分：第k组（k从0到n-1）包含k+1个元素，每个元素是前一组最后一个值依次加上a[0]到a[k]的累加和。
2. 定义前缀和prefix[j]为a[0]到a[j]的累加值，那么第k组的所有元素可表示为「前k组前缀和的累加值 + prefix[j]」（j从0到k）。
3. 只需维护三个变量：当前前缀和的最大值、前k组前缀和的累加值、全局最大值，即可在一次遍历中求出结果，无需存储整个序列b。

实现代码 #

def find_max(a):
    if not a:
        return 0
    
    n = len(a)
    # 计算前缀和数组
    prefix = [0] * n
    prefix[0] = a[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + a[i]
    
    global_max = 0  # 初始值对应b[0]
    s_prev = 0  # 前k组前缀和的累加值，初始为0（对应k=0时的前序和）
    current_max_prefix = prefix[0]
    
    for k in range(n):
        current_prefix = prefix[k]
        # 更新当前前缀和的最大值（prefix[0..k]中的最大值）
        current_max_prefix = max(current_max_prefix, current_prefix)
        # 计算当前组的最大值
        current_group_max = s_prev + current_max_prefix
        # 更新全局最大值
        if current_group_max > global_max:
            global_max = current_group_max
        # 更新前k组前缀和的累加值
        s_prev += current_prefix
    
    return global_max

空间优化（O(1)空间复杂度） #

如果不需要保留原数组a，可以直接在原数组上计算前缀和，省去额外的prefix数组：

def find_max(a):
    if not a:
        return 0
    
    n = len(a)
    # 原地计算前缀和
    for i in range(1, n):
        a[i] += a[i-1]
    
    global_max = 0
    s_prev = 0
    current_max_prefix = a[0]
    
    for k in range(n):
        current_prefix = a[k]
        current_max_prefix = max(current_max_prefix, current_prefix)
        current_group_max = s_prev + current_max_prefix
        if current_group_max > global_max:
            global_max = current_group_max
        s_prev += current_prefix
    
    return global_max

内容的提问来源于stack exchange，提问作者Get_good32