数学考试

数学考试

题目分析:

1. 涉及算法：前缀和，区间求和
2. 题目要求分为两个不连续的区间，[l,l + k - 1],[r,r + k - 1](r >= l + k);
3. 枚举每两个适合的区间，(i - k + 1,i),(i + 1,i + k)
4. 前缀和的区间求和为s[r] - s[l - 1];

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 2e5 + 10;

int t;
ll n,k;
ll a[N],s[N];

int main() {
    cin >> t;
    while(t -- ){
        cin >> n >> k;
        mm(s,0);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];    
        for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
        ll m1 = -1e18,ans = -1e18;
        for(int i = k; i + k <= n; i ++ ){
            m1 = max(m1,s[i] - s[i - k]);
            ans = max(ans,m1 + s[i + k] - s[i]);
        }
        cout<<ans<<endl;
    }    
    return 0;
}