题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
deque<ll> q;
ll dp[N][2],s[N];//s是前缀和数组 
/*
单调队列：
1、移除队首中超过窗口的元素
pop_front()
2、移除队尾中比当前值小的元素
pop_back()
3、从队尾插入新元素
push_back()
4、访问队首
front()
*/ 
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		ll x;
		cin>>x;
		s[i] = s[i-1] + x;//前缀和 
	} 
	//初始化，前 0个数 
	dp[0][0] = 0;
	dp[0][1] = -1e9;
	//单调队列
	q.push_back(0);
	//遍历每个数 i 到底选不选！ 
	for(int i=1;i<=n;i++){
		//默认不选
		dp[i][0] = max(dp[i-1][0],dp[i-1][1]); 
		//考虑选择第i个数，找 t？ 
		//单调队列的维护
		while(!q.empty() && q.front() < i-k){
			q.pop_front();//维护队首，移除超出窗口[i-k,i-1]外的元素 
		}
		ll b = q.front();
		dp[i][1] = dp[b][0]-s[b]+s[i];
		//维护队尾，保证单调队列递减
		ll cur = dp[i][0]-s[i];//当前i下标对应的候选值
		while(!q.empty() && cur > dp[q.back()][0]-s[q.back()]){
			q.pop_back();
		}
		q.push_back(i);//维护完成，可以添加 i下标		 
	} 
	cout<<max(dp[n][0],dp[n][1]);	
	
	return 0;
}