A contiguous subsequence of largest sum
*idea from Leonid Chindelevitch
def largest_sum_contiguous_subsequence(l):
"""l is a list of numbers;
The function returns a contiguous subsequence of largest sum"""
u=[l[0]] #u[i] denotes the best sum of a contiguous subsequence ending at l[i] that does include l[i]
v=[0] #v[i] denotes the best sum of a contiguous subsequence ending at l[i] that doesn't include l[i]
for i in range(1,len(l)):
u.append(max(u[i-1],0)+l[i])
v.append(max(u[i-1],v[i-1]))
return max(u[-1],v[-1])
A simpler algorithm is as follows (idea from Axel Andersson)
def subseq(A):
max1 = 0
sum1 = 0
curAr = []
maxAr = []
for i in range(len(A)):
sum1 += A[i]
curAr.append(A[i])
if sum1 > max1:
max1 = sum1
maxAr = curAr[:]
elif sum1 <= 0:
sum1 = 0
curAr = []
return maxAr