前缀和数组:计算前缀和数组 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; } }