题目

题意：在长为n的序列a[]中选2段不连续长度为k的区间使区间和最大。n ≤ 2e5

做法

代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const ll INF = 1e18;
int n, k, m, a[N];
ll prefix[N], rmq[N][18];
void init_rmq(void){
    for (int j = 1; (1<<j) <= m; ++j){
        for (int i = 1; i+(1<<j)-1 <= m; ++i){
            rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }
}
ll ask_rmq(int l, int r){
    if (l > r) return -INF;
    int k = log2(r-l+1);
    return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> k;
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
            prefix[i] = prefix[i-1]+a[i];
        }
        m = n-k+1;
        for (int i = 1; i <= m; ++i){
            rmq[i][0] = prefix[i+k-1]-prefix[i-1];
        }
        init_rmq();
        ll ans = -INF;
        for (int i = 1; i <= m; ++i){
            ans = max(ans, rmq[i][0]+ask_rmq(i+k, m));
        }
        cout << ans << endl;
    }
    return 0;
}