链接：https://ac.nowcoder.com/acm/problem/15553
今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。
链接：https://ac.nowcoder.com/acm/problem/15553
来源：牛客网
输入描述:
第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）
输出描述:
输出一个整数，qwb能获得的最大分数
示例1
输出
6 7
一开始想到了前缀和，但是一直TL，因为一直在枚举,其实只有不断动态维护前面的最大区间值即可
#include<bits/stdc++.h> using namespace std; int n,a[200002],k; long long sum[200002]; long long maxz; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin>>T; while(T--){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } maxz=-1e15; long long ans=-1e15; for(int i=k;i+k<=n;i++) { ans=max(ans,sum[i]-sum[i-k]);//维护前面的最大值 maxz=(maxz,ans+sum[i+k]-sum[i]); } cout<<maxz<<endl; } }
原文链接: https://www.cnblogs.com/Charls/p/12931922.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/350069
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
