数学考试

题目要求求两个连续的区间和的最大值，我们可以先处理出两块区间和，然后加一起取max

法一、将两块区间和处理出来

fl[i]表示从1走到i位置，区间和长度为k的最大区间和
fr[i]表示从n走到i位置，区间和长度为k的最大区间和

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 200010;
const LL INF = 1e18;

int n, k;
LL fl[N], fr[N];
LL s[N];

int main() {
    int T; scanf("%d", &T);

    while (T -- ) {
      scanf("%d%d", &n, &k);
      for (int i = 1; i <= n; i ++ ) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
        fl[i] = fr[i] = -INF;
      }

      //表示[i - k + 1, i]的区间和
      for (int i = k; i <= n - k; i ++ )
        fl[i] = max(fl[i - 1], s[i] - s[i - k]);
      //表示[i, i + k - 1]的区间和
      for (int i = n - k + 1; i >= k + 1; i -- )
        fr[i] = max(fr[i + 1], s[i + k - 1] - s[i - 1]);

      LL ans = -INF;
      for (int i = k + 1; i <= n - k + 1; i ++ )
        ans = max(ans, fl[i - 1] + fr[i]);

      printf("%lld\n", ans);
    }
}

法二、先处理出右侧区间，遍历左区间

f[i]表示从n走到i位置的区间和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, k;
LL a[N];
LL s[N];
LL f[N];

int main() {
  int T; cin >> T;
  while (T -- ) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ) {
      scanf("%lld", &a[i]);
      s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i ++ )
      f[i] = -1e18;
    // memset(f, -0x3f, sizeof f);
    //右区间为[i, i + k - 1]的区间和中的最大值
    //f[n - k + 2] 就是等于0的，一开始没被更
    for (int i = n - k + 1; i >= k; i -- ){
      f[i] = max(f[i + 1], s[i + k - 1] - s[i - 1]);
    }

    LL ans = -1e18;
    //左区间为[i - k, i - 1]的区间和
    for (int i = k + 1; i <= n - k + 1; i ++ )
      ans = max(ans, s[i - 1] - s[i - k - 1] + f[i]);

    printf("%lld\n", ans);
  }

  return 0;
}

法三，简化

由上面的两个方法，我们看出，我们做的也是我们需要的就是让两个区间和最大化
若以i为分界点，就是求i之前的长度为k的区间和的最大值，和i后面的长度为k的区间和的最大值，我们可以一遍扫过

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 200010;
const LL INF = 1e18;

int n, k;
LL fl[N], fr[N];
LL s[N];

int main() {
    int T; scanf("%d", &T);

    while (T -- ) {
      scanf("%d%d", &n, &k);
      for (int i = 1; i <= n; i ++ ) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
        fl[i] = fr[i] = -INF;
      }

      LL ans = -INF, res = -INF;
      //以i为界，res表示从0开始，走到i的最大的长度为k的区间和
      for (int i = k; i <= n - k; i ++ ) {
        //s[i] - s[i - k]表示[i - k + 1, i]的区间和
        res = max(res, s[i] - s[i - k]);
        //s[i + k] - s[i]表示[i + 1, i + k]的区间和
        ans = max(ans, res + s[i + k] - s[i]);
      }

      printf("%lld\n", ans);
    }
}