【每日一题】前缀和、滑动窗口

题目：https://ac.nowcoder.com/acm/problem/15553

统计一个数前面的连续k个数和 premax

后面最大的连续k个数和 sufmax

最后遍历一遍，

ans=max(ans,preans+sufmax[i+1]);

ans=max(ans,preans+premax[i-k]);

【心得】

这里写复杂了=。= 还是代码写的太少

直接前缀和就可以 sum[i]-sum[i-k]；sum[i+k-1]-sum[i-1]

我这里是用滑动窗口写的=====

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LONGLONGMIN -922337203685477580
const int maxn = 2e5 + 10;

int nums[maxn];
int n, k;
ll premax[maxn];//以x结尾
ll sufmax[maxn];//以x开始

ll solve()
{
    ll preans = 0, sufans = 0;
    ll ans = 0;
    ll prevpre=LONGLONGMIN, prevsuf=LONGLONGMIN;
    int i;
    for (i = 0; i < k; ++i)
        preans += nums[i];
    for (i = n - 1; i >= n - k; --i)
        sufans += nums[i];
    premax[k-1]=preans; 
    sufmax[n-k]=sufans;

    for(int en=n-2;en>=k-1;en--){
        int st=en-k+1;
        sufans -= nums[en+1];
        sufans += nums[st];
        sufmax[st] = max(sufmax[st+1],sufans);
    }
    for(int st=1;st<=n-k;++st){
        int en = st+k-1;
        preans -= nums[st-1];
        preans += nums[en];
        premax[en]=max(premax[en-1],preans);
    }
    
    preans=premax[k-1];
    for(int i=k-1;i<n;++i){
        if(i==k-1) ans=max(ans,preans+sufmax[k]);
        else{
            preans -= nums[i-k];
            preans += nums[i];
            ans=max(ans,preans+sufmax[i+1]);
            ans=max(ans,preans+premax[i-k]);
        }
    }
    return ans;
}
int main(void)
{
    int T;
    cin >> T;
    while (T--) {       
        cin >> n >> k;
        ll sum=0;
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];sum+=nums[i];
        }
        
        if (2 * k == n) {
            cout << sum << endl;
            continue;
        }

        for(int i = 0;i<=n;++i){
            premax[i]=sufmax[i]=LONGLONGMIN;
        }
        cout << solve() << endl;
    }

    return 0;
}

【简洁版本】

注意：

//处理前缀和题目，让nums数组下标从1开始更简单 此时[i,j]的和为sum[j]-sum[i-1]
//边界情况也更容易处理 [1,3]的和就是sum[3]-sum[0] sum初始化为0即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LONGLONGMIN -922337203685477580
const int maxn = 2e5 + 10;

int nums[maxn];
int n, k;
ll premax[maxn];  // 以x结尾
ll sufmax[maxn];  // 以x开始
ll sum[maxn];

int main(void)
{
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        //处理前缀和题目，让nums数组下标从1开始更简单 此时[i,j]的和为sum[j]-sum[i-1]
        //边界情况也更容易处理 [1,3]的和就是sum[3]-sum[0] sum初始化为0即可
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; ++i) {
            cin >> nums[i];
            sum[i] += nums[i] + sum[i - 1];
        }

        if (2 * k == n) {
            cout << sum[n] << endl;
            continue;
        }
        memset(premax, -0x7f, sizeof(premax));
        memset(sufmax, -0x7f, sizeof(premax));
        for (int en = n; en >= k; en--) {
            int st = en - k + 1;
            sufmax[st] = max(sufmax[st + 1], sum[en] - sum[st-1]);
        }
        for (int st = 1; st <= n - k+1; ++st) {
            int en = st + k - 1;
            premax[en] = max(premax[en - 1], sum[en] - sum[st-1]);
        }
        ll ans=0;
        for (int en = k; en <= n; ++en) {
            ans = max(ans, sum[en]-sum[en-k] + sufmax[en + 1]);
            ans = max(ans, sum[en]-sum[en-k] + premax[en - k]);
            
        }
        cout<<ans<<endl;
    }

    return 0;
}