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