【每日一题】 数学考试

题意：
给定一个长度为n的序列，选取两个不相交且长度为k的区间，求两个区间的元素之和的最大值。
思路：
记sum_right[i]为以i为右界且长度为k的区间内元素和，记left_max[i]为左界大于等于i的所有区间元素和的最大值。一趟遍历可求出sum_right，再利用其求出left_max，最后求得ans=max{sum_right[i]+left_max[i+1]};
代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;
const int inf=2e9+9;
const int maxn=2e5+9;
const int maxx=2e5+9;



int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&ar[i]);
        ll tmp=0;
        for(int i=0;i<k;i++) tmp+=ar[i];
        sum_right[k-1]=tmp;
        for(int i=k;i<n;i++)
            tmp+=ar[i]-ar[i-k],sum_right[i]=tmp;
        left_max[n-k+1]=-inf;
        for(int i=n-k;i>=k;i--) left_max[i]=max(sum_right[i+k-1],left_max[i+1]);
        ll ans=sum_right[k-1]+left_max[k];
        for(int i=k;i<n-k;i++) ans=max(ans,sum_right[i]+left_max[i+1]);
        printf("%lld\n",ans);
    }
}