1、累加和最大的子序列
def maxsub(lists):
cur=0
maxsum=lists[0]
for i in lists:
if cur<0:
cur=0
cur+=i
if cur>maxsum:
maxsum=cur
return maxsum
2、累加和最大的子数组
######## n
########
########
m
O(n2*m)
进一步可以取n和m中较小的数作为平方项。进一步减小复杂度。字数组数目是
def maxsub(mat):
maxsum=float("-inf") #min
for i in xrange(len(mat[0])):
temprow = []
for j in xrange(i,len(mat[0])):
if temprow==[]:
temprow=mat[j]
else:
temprow=map(lambda (a,b):a+b, zip(temprow,mat[j]))
print temprow
cur=0
for item in temprow:
if cur<0:
cur=0
cur+=item
if cur>maxsum:
maxsum=cur
