题目描述

今天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）。

输入描述: 

第一行一个整数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

输入 

2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出 

6
7

思路

求出前缀和之后，一个循环去找最大区间和和最大的答案，注意两个区间不能重叠。注意开long long！！

代码 

//数学考试(贪心 前缀和)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
typedef long long ll;

ll s[N]; 

int main()
{
 	int t;
 	scanf("%d" , &t);
 	
 	while(t--)
 	{
		int n , k;
		scanf("%d %d" , &n , &k);
		for(int i = 1 ; i <= n ; i++)
		{
			scanf("%lld" , &s[i]);
			s[i] += s[i - 1];	 
		}	 

		ll ans = -1e18 , maxn = -1e18;
		for(int i = k ; i <= n - k ; i++)
		{
			maxn = max(maxn , s[i] - s[i - k]);
			ans = max(ans , maxn + s[i + k] - s[i]);
		}
		
		printf("%lld\n" , ans);
	}
	return 0; 
}