前缀和数组:计算前缀和数组 s,其中 s[i] 表示 a[1] 到 a[i] 的和。这样,任意区间 [l, r] 的和可以快速计算为 s[r] - s[l-1]。
滑动窗口:对于每个 i,计算 a[i] + a[i-1] + ... + a[max(1, i-9)]。这可以通过前缀和数组快速计算:
如果 i >= 10,则最近十次的和是 s[i] - s[i-10]。
如果 i < 10,则最近十次的和是 s[i]。
遍历所有可能的 i:计算每个 i 的真实 token 用量,并记录最大值。
优化
直接计算每个 i 的十次和可能会重复计算,使用前缀和可以避免重复计算。
滑动窗口:对于每个 i,计算 a[i] + a[i-1] + ... + a[max(1, i-9)]。这可以通过前缀和数组快速计算:
如果 i >= 10,则最近十次的和是 s[i] - s[i-10]。
如果 i < 10,则最近十次的和是 s[i]。
遍历所有可能的 i:计算每个 i 的真实 token 用量,并记录最大值。
优化
直接计算每个 i 的十次和可能会重复计算,使用前缀和可以避免重复计算。
前缀和数组:计算 s 数组,其中 s[i] 是 a[1..i] 的和。
#include<bits/stdc++.h>
using namespace std;
long long int n,m,num[100000000],s[100000000],maxx=-1;
int main()
{
cin>>n;
if(n<=10)\
{
for(int i=1;i<=10;i++)
{
cin>>num[i];
m+=num[i];
}
cout<<m;
}
else
{
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>num[i];
s[i]=s[i-1]+num[i];
}
maxx=s[10];
for(int i=11;i<=n;i++)
{
if((s[i]-s[i-10])>maxx)
{
maxx=s[i]-s[i-10];
}
}
cout<<maxx;
}
}

京公网安备 11010502036488号