描述
给出n个数排成一排,你可以任意选出连续的L个数字求和。例如:
n=5 L = 4
-20 30 80 50 40
连续取L个数的方法有两种。
1、取前4个数-20 30 80 50 和为140。
2、取后4个数30 80 50 40 和为200。
请你找出最大和是多少,上例结果应该为200。
输入描述
第1行为两正整数n和L表示数列数字个数和取的长度;
第2行n个整数空格分隔,表示数列中的每个元素,数字在-100到100之间的整数。
输出描述
输出一个整数,最大的数字和。
样例输入 1
5 4 -20 30 80 50 40
样例输出 1
200
提示
数据范围与提示
30%的数据1≤L≤n≤100。
50%的数据1≤L≤n≤10000。
100%的数据 1≤L≤n≤1000000。
上代码!
#include<bits/stdc++.h>
using namespace std;
long long a[5000001],s[5000001]={};
int main(){
int n,m,x,y,max=-100000,b,t;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
b=m;
for(int i=0;i<=n-m;i++){
t=s[b]-s[i];
if(t>max){
max=t;
x=i+1;
y=i+m;
}
b++;
}
cout<<max;
return 0;
}