2、累加和最大的子序列、累加和最大的子数组

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(n²*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