In [2]:
def maxsum(l):
    '''最大子序列和问题'''
    m=s=0
    for i in l:
        s=max(s, 0)
        s+=i
        m=max(m, s)
    return m
In [3]:
def maxprod(l):
    '''最大子序列积问题'''
    m=pos=0
    neg=0
    for i in l:
        pos=max(1, pos)*i
        neg=neg*i
        if i<0:
            pos, neg=neg, pos
        m=max(m, pos)
    return m
In [45]:
def minabssum(l, pos=False):
    '''pos
    True    最小正子序列
    False   最小绝对值子序列问题'''
    cum=cumsum(l)
    s=[[cum[i], i+1] for i in range(len(l))]
    s.append([0, 0])
    t=sorted(s)
    print(t)
    minabs=inf
    for i in range(len(l)):
        if((not pos) or t[i+1][1]>t[i][1]):
            minabs=min(minabs, t[i+1][0]-t[i][0])
    return minabs

Comments

comments powered by Disqus