Here is a recurrence that seems to be pretty fast for random data but slower with largely sorted data). With 3000 elements, it seems about 10-20 times faster than Amo Robb's maxsub3 function (for random, not sorted data). The repl includes accuracy tests against brute force as well. The recurrence is naive - some of the backwards runs could have the best solution looked up based on the max_subarray threshold.
Let f(i, is_max, subarray_max) represent the largest sum ending at the ith element,
where is_max indicates if the element is the maximum, and subarray_max is the
maximum of the subarray. Then:
# max isn't used if the element
# ending the subarray is fixed
# as the maximum.
def f(A, i, is_max, subarray_max, memo, ps, pfxs):
key = str((i, is_max, subarray_max))
if key in memo:
return memo[key]
if is_max:
if i == 0 or A[i-1] > A[i]:
return 0
result = f(A, i - 1, False, A[i], memo, ps, pfxs)
memo[key] = result
return result
# not is_max
if i == 0:
if A[i] > subarray_max:
return 0
return max(0, A[i])
# If max is not defined,
# we MUST include all previous
# elements until the previous equal or
# higher element. If there is no
# previous equal or higher element,
# return -Infinity because a subarray
# ending at A[i] cannot correspond
# with false is_max.
if subarray_max == None:
prev = ps[i]
if prev == -1:
return -float('inf')
best = -float('inf')
temp = ps[i]
while ps[temp] != -1:
candidate = pfxs[i] - pfxs[temp] + f(A, temp, True, None, memo, ps, pfxs)
if candidate > best:
best = candidate
# The prev equal or higher could still
# be smaller to another.
candidate = pfxs[i] - pfxs[temp] + f(A, temp, False, None, memo, ps, pfxs)
if candidate > best:
best = candidate
temp = ps[temp]
candidate = pfxs[i] - pfxs[temp] + f(A, temp, True, None, memo, ps, pfxs)
if candidate > best:
best = candidate
memo[key] = best
return best
# If max is defined, the previous
# equal or higher could be higher
# than max, in which case we need
# not include all elements in between.
if A[i] > subarray_max:
return 0
result = max(0, A[i] + f(A, i - 1, False, subarray_max, memo, ps, pfxs))
memo[key] = result
return result
def g(A):
memo = {}
best = -float('inf')
ps = find_prev_greater_elements(A)
pfxs = [A[0]] + [None] * len(A)
for i in range(1, len(A)):
pfxs[i] = A[i] + pfxs[i-1]
for i in range(len(A)):
best = max(best, f(A, i, True, None, memo, ps, pfxs))
if i > 0:
best = max(best, f(A, i, False, None, memo, ps, pfxs))
return best
# Adapted from https://stackoverflow.com/a/9495815/2034787
def find_prev_greater_elements(xs):
ys=[-1 for x in xs]
stack=[]
for i in range(len(xs)-1, -1, -1):
while len(stack)>0 and xs[i] >= xs[stack[-1]]:
ys[stack.pop()]=i
stack.append(i)
return ys
