牛客区间求和、枚举、贪心题---数学考试

数学考试

• 区间求和问题可以想到一个常用算法：前缀和。区间的和可以用方便地求出。
• 维护第一个长度为k的最大值，枚举第二个长度为k的起点，答案就是max(ans,当前长度为k的序列和+第一个长度为k的序列和)

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define maxn 200005
#define inf 0x3f3f3f3f
#define INF 1e18

ll a[maxn];
int main(){
    int t;cin>>t;
    while(t--){
       int n,k;cin>>n>>k;
       for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
       ll max0=-INF,ans=-INF; 
       for(int i=k;i+k<=n;i++){
       	max0=max(max0,a[i]-a[i-k]);
       	ans=max(ans,a[i+k]-a[i]+max0);
       }
	   cout<<ans<<"
";
    }
    return 0;
}