我有长度为 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)
这是其他版本,应该在 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