Python 特定 struct 中的最大元素

发布于02月08日

我有长度为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) time and O(1) space.个

考虑这个(外环)回合:

b[4] = b[3] + a[0]   = b[3] + a[0]
b[5] = b[4] + a[1]   = b[3] + a[0] + a[1]
b[6] = b[5] + a[2]   = b[3] + a[0] + a[1] + a[2]

你不需要所有这些.只要知道就够了:

它们中的最大数量.也就是b[3] + max(prefix sums of a[:3]).
最后一个，b[6] = b[3] + sum(a[:3])个.因为你在下一轮比赛中需要这个.

一般来说，要找出每轮的最大值，知道以下内容就足够了:

该回合开始时的值为b.
最大前缀SUM为a[:...].

把它们加在一起，就能知道整轮的最大值是b.并返回这些轮数最大值中的最大值.

对于每一轮，我们可以在O(1)时间内更新这些值:

def find_max_linear(a):
  b = max_b = 0 
  sum_a = max_sum_a = 0
  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

测试:

import random
for _ in range(10):
  a = random.choices(range(-100, 101), k=100)
  expect = find_max(a)
  result = find_max_linear(a)
  print(result == expect, expect, result)

输出(Attempt This Online!):

True 8277 8277
True 2285 2285
True 5061 5061
True 19261 19261
True 0 0
True 0 0
True 47045 47045
True 531 531
True 703 703
True 24073 24073

时间复杂度为O(n)，空间复杂度为O(n).

from itertools import accumulate as acc
from operator import add

def find_max_linear(a):
  return max(0, *map(add, acc(acc(a), initial=0), acc(acc(a), max)))

或者分成几行，配上 comments :

def find_max_linear(a):
  return max(0, *map(
    add,
    acc(acc(a), initial=0),  # each round's initial b-value
    acc(acc(a), max)         # each round's max prefix sum of a[:...]
  ))

Attempt This Online!个