题目目的说明

我们需要找出一段长度为$m$的连续子序列，使得他们的加权和最大。

最最最暴力的方法

不就是枚举吗？枚举长度为$m$的序列，每次移动一格。如下图。

暴力的代码实现 O(nm)

#include<iostream>
using namespace std;

const int N = 200050;

long long b[N];
long long res = 0;
int n , m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    
    for(int i = 1; i <= n - m + 1; i++)
    {
        long long tmp = 0;
        for(int j = i; j <= i + m - 1; j++)
        {
            tmp += (j - i + 1) * b[j];   //题目要求加权求和
        }
        res = max(tmp, res);
    }
    cout<<res;
    return 0;
}

一交！AC！！！！（我在想屁吃） 被超时了！

所以我们就来优化了

我们要根据前面那张图来找找规律如下图所示

所以我们得到了最终方案

我们用前缀和先预处理一次这样的话，我们在求区间和的时候我们就达到了o(1)的时间复杂度。其他思路还是一样的

代码实现O(n)

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 200050;

long long b[N];
long long f[N];
long long a[N];
long long n , m;
int main()
{
    cin >> n >> m;
    //读入数据并预处理前缀和
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
        a[i] = a[i - 1] + b[i];
    }
    // 初始化我们的第一个求和数组
    for(int i = 1; i <= m ; i++)
    {
        f[1] += i * b[i];
    }
    long long res = f[1];   //把第一个值先加进去

   //然后开始递推计算
    for(int i = 2; i <= n - m + 1; i++)
    {
        f[i] = f[i - 1] - (a[i - 2 + m] - a[i - 2]);
        f[i] += m * b[i + m - 1];
        res = max(res, f[i]);
    }
    printf("%lld", res);
    return 0;
}