小编dan*_*dan的帖子

给定一个正整数数组。如何找到L具有max和的长度的子序列，该子序列的两个相邻元素之间的距离不超过K

我有以下解决方案，但不知道如何考虑长度L。

1 <= N <= 100000，1 <= L <= 200，1 <= K <= N

f [i]包含以i结尾的子序列的最大和。

for i in range(K, N)
    f[i] = INT_MIN
    for j in range(1, K+1)
        f[i] = max(f[i], f[i-j] + a[i])
return max(f)

我需要在 python 中构建一个循环缓冲区作为双端队列，并进行高效搜索（不是 O(n) el in deque，而是像 set() 中那样的 O(1) ）

from collections import deque 
deque = deque(maxlen=10) # in my case maxlen=1000
for i in range(20):
    deque.append(i)
deque 
Out[1]: deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
10 in deque # but it takes O(n), I need O(1)
Out[1]: True

我想我需要维护一个单独的字典来查找，并在双端队列满后从中删除，但不明白如何做。我不需要从双端队列的中间删除，只需像append双端队列那样进行快速查找即可。