单调队列-连续子序列的最大和

题目描述

给定一个长度为n的整数序列，请找出长度不超过m的连续子序列的最大和。

例如，数组{2,-3,5,2,-4,-1,8}，m取3，那么长度不超过3的连续子序列的最大和为8。

代码详解

展开查看

a= [0, 2, -3, 5, 2, -4, -1, 8]
s = [0]
x = 0
for i in range(1, len(a)):
    x += a[i]
    s.append(x)

m = 3
ans = s[1]
for i in range(1, len(s)):
    mi = 1000000
    for j in range(i-m, i):
        if j >= 0:
            mi = min(mi, s[j])
    ans = max(ans, s[i] - mi)

print(ans)

展开查看

#单调队列
a= [0, 2, -3, 5, 2, -4, -1, 8]
q = [0,1,2,3,4,5,6,7]
s = [0]
x = 0
m = 3
for i in range(1, len(a)):
    x += a[i]
    s.append(x)

h = 0
t = 0
ans = s[1]
for i in range(1, len(a)):
    #q[h]不在窗口[i-m, i-1]内，队头出队
    if h<=t and q[h]<i-m:
        h += 1
    #使用队头最小值
    ans = max(ans, s[i]-s[q[h]])
    #当前值<=队尾值，队尾出队
    while h<=t and s[i]<=s[q[t]]:
        t -= 1
    #下标入队，便于队头出队
    t+=1
    q[t] = i
print(ans)

运行结果

展开查看