数学考试

数学考试

题目描述

今天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能获得的最大分数

输入

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

输出

6
7

题目大意

n道题，不做完，做2k道，连续两个不重合长度为k的区间，分数最大

思路

dp+前缀和
1.先求前缀和
2.从前到后求出数组下标i前的最大k长度区间和，不断更新（前一个的最大和最当前的和进行比较）
3从后到前求出数组下标i后的最大k长度区间和，不断更新（后一个的最大和最当前的和进行比较）
4.枚举所有i的前后最大值的和，找出最大和

错误思路

先求最大的k长度区间和，再从两边找第二大的k长度区间和
错误原因：情况考虑不全。

/*#include<bits/stdc++.h>错误思路
using namespace std;
int num[2000005];
struct date{
    int a;
    int head;
    int wei;
}sum[2000005];
bool cmp(date a,date b)
{
    return a.a>b.a;
}
int main()
{
    //n道题 每道ai分 不全部做完，做2k道题，分数尽可能大
    //前缀和
    //不重合的两个区间 
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<2000005;i++)//初始化 
        {
            num[i]=0;
            sum[i].a=0;
            sum[i].head=0;
            sum[i].wei=0;
        }
        int n=0,k=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
        }
        for(int i=0;i<k;i++)
        {
            sum[0].a=sum[0].a+num[i];
        }
        sum[0].head=0;
        sum[0].wei=k-1;
        //printf("sum[0]=%d\n",sum[0]); 
        for(int i=1;i<n&&sum[i].wei<n;i++)
        {
            sum[i].a=sum[i-1].a+num[sum[i-1].wei+1]-num[sum[i-1].head];
            sum[i].head=sum[i-1].head+1;
            sum[i].wei=sum[i-1].wei+1;
        }
        sort(sum,sum+n,cmp);
        int max=sum[0].a;
        sum[0].a=0;
        int maxn=0;
        for(int i=0;i<n;i++)
        {
            if(sum[i].a>maxn)
            {
                if(sum[i].head>sum[0].wei||sum[i].wei<sum[0].head)
                {
                    maxn=sum[i].a;
                }
            }
        }
        printf("%d\n",max+maxn);
     } 
    return 0;
 } */
#include<bits/stdc++.h>
using namespace std;
long long int sum[200005];
long long int f[200005];
long long int s[200005];
int main()
{
    //dp记录下标i前最大的值，i后最大的值 
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        long long ans=-1e18;
        scanf("%d%d",&n,&k);
        memset(f,-0x7f,sizeof(f)) ;
        memset(s,-0x7f,sizeof(s));
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&sum[i]);
            sum[i]=sum[i]+sum[i-1];
        }
        for(int i=k;i<=n-k;i++)
        {
            f[i]=max(f[i-1],sum[i]-sum[i-k]);
        }
        for(int i=n-k+1;i>=k+1;i--)
        {
            s[i]=max(s[i+1],sum[i+k-1]-sum[i-1]);
        }
        for(int i=k;i<=n-k;i++)
        {
            ans=max(ans,f[i]+s[i+1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}