思路
使用前缀和数组s[N]
和单调队列deque
存储下标进行DP优化
c++ 单调队列优化DP
#include <bits/stdc++.h>
using namespace std;
const int N=300005;
int n, m;
int s[N];
int main(){
memset(s, 0x00, sizeof s);
cin>>n>>m;
for(int i=1; i<=n; ++i){
cin>>s[i];
s[i]+=s[i-1];
}
int res=INT32_MIN;
deque<int> q;
for(int i=1; i<=n; ++i){
if(!q.empty() && q.front()<i-m) q.pop_front(); // 如果队首元素已经到了窗口外, 则弹出
res=max(res, s[i]-s[q.front()]);
while(!q.empty() && s[q.back()]>=s[i]) q.pop_back();
q.push_back(i);
}
cout<<res<<endl;
return 0;
}
python 单调队列优化DP
from typing import List
class Solution:
def main(self, n:int, m:int, a:List[int]):
s, q=[0 for _ in range(n+1)], [0]
for i in range(1, n+1):
s[i]=s[i-1]+a[i-1]
res=float('-inf')
for i in range(1, n+1):
if q[0]<i-m: q.pop(0)
res=max(res, s[i]-s[q[0]])
while q and s[q[-1]]>=s[i]: q.pop(-1)
q.append(i)
print(res)
if __name__ == "__main__":
n, m=map(int, input().split())
a=list(map(int, input().split()))
sol=Solution()
sol.main(n, m, a)
老哥,为什么顺序不能变
不先出队子序列和就会计算不应该出现在窗口里的元素