特定结构中的最大元素

Question

我有长度为 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[8] = b[7] + a[1]
b[9] = b[8] + a[2]
b[10] = b[9] + a[3]
#etc.

a 可以包含非正值。我需要找到 b 的最大元素。我只想出了 O(n^2) 的解决方案。有没有更快的方法？

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)

Answer 1

这是其他版本，应该在 O(n) 内运行：

def get_a(a):
    i, mx = 0, 0
    while True:
        yield a[i]
        i += 1
        if i > mx:
            mx += 1
            i = 0
        if mx >= len(a):
            return


def find_max_2(a):
    x = get_a(a)
    yield (last := 0)
    try:
        while True:
            yield (last := last + next(x))
    except StopIteration:
        return


a = [1, 3, 1, 2]
print(max(find_max_2(a)))

打印：

17