算法入门课第一节--练习--数学考试 题解

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

Solution

思路：

一开始wa了，想错了以为直接排个序然后倒叙2k累和就行，wa第一次以为是没开long long，开了之后还只有0.5的正确率，发现原来想错了。
其实一开始就想到了前缀和，但是傻乎乎的没用。个人认为是枚举+前缀和，但是大多数人说是DP+前缀和，都有道理。主体就是在前n-k个长度为k的连续区间里找到两个不交错的区间，使得他们的和最大。

代码

#include<bits/stdc++.h>
#define ll long long
#define max(a, b) (a > b ? a : b)
using namespace std;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll n,k;
        scanf("%lld %lld",&n,&k);
        ll sum[1+n];
        sum[0] = 0;
        for(int i = 1 ;i<n+1;i++) {
            scanf("%lld",&sum[i]);
            sum[i] += sum[i-1];
        }
        ll maxx=-1e18,ans=-1e18;
        for(int i = k;i+k<=n;i++){
            maxx = max(maxx,sum[i]-sum[i-k]); //找到从k开始到目前最大的区间和
            ans = max(ans,maxx+sum[i+k]-sum[i]);//再从k开始找在k后面最大的区间与前面最大区间和的最大值
        }
        cout<<ans<<endl;
    }
}