题目描述:
子曰:“三人行,必有我师”。人越多,可请教的也越多。假设有 n 个人排成一列,每个人的知识值是一个整数,现在我们想要选取 k 个连续的人,使得这 k 个人的知识值之和最大,请你输出这个最大值。
输入:
输入包含 2 行:
第一行有两个整数 n,k(1 ≤ k≤ n ≤ 10^5),表示人的总数和要选的连续的人数
第二行有 n 个空格隔开的整数 ti(1 ≤ ti ≤ 10^9),为每个人的知识值
输出:
输出为一个整数,为连续 k 个人的知识值之和的最大值
样例输入:
5 3
1 2 2 3 1
样例输出:
7
解析:
这道题其实重点在于前缀和,要外设一个前缀和数组,例如:
int n,k;
long long a[100001],sum[100001];//这道题必须用long long
设完变量就可以输入了,顺便弄好前缀和:
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
接下来是找出前缀和中最大的:
long long maxn=0;
for(int i=1;i<=n;i++)
{
maxn=max(maxn,sum[i+k-1]-sum[i-1]);
}
找完后便是输出了:
cout<<maxn;
完整代码:
#include<iostream>
using namespace std;
long long a[100001],sum[100001];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
long long maxn=0;
for(int i=1;i<=n;i++)
{
maxn=max(maxn,sum[i+k-1]-sum[i-1]);
}
cout<<maxn;
return 0;
}