网站建设静态部分实训总结,做网站一般用什么系统,贵州省住房和城乡建设部网站,个人域名 公司网站题目描述
给你一个数列a1,a2,...,an,求m个连续数字组成的子段和最大值。
输入
有多个样例#xff0c;每个样例的第一行是两个整数n和m#xff0c;(1≤m≤n;≤100,000)。如果n和m为0表示输入结束#xff0c;这个样例不需要处理。第二行是n个整数ai#xff0c;0≤ai≤1000…题目描述
给你一个数列a1,a2,...,an,求m个连续数字组成的子段和最大值。
输入
有多个样例每个样例的第一行是两个整数n和m(1≤m≤n;≤100,000)。如果n和m为0表示输入结束这个样例不需要处理。第二行是n个整数ai0≤ai≤10000。
输出
每行输出一个整数即样例的结果。
样例输入
6 3
1 2 3 4 5 6
6 3
1 2 3 3 2 1
0 0
样例输出
15
8AC代码
#includestdio.h
#define N 100005
int main(){int n,m;while(scanf(%d%d,n,m)!EOF){if(m0n0)break;int a[N]{};int i,j;for(i0;in;i){scanf(%d,a[i]);}for(i0;in;i){a[i]a[i-1];}int maxa[n-1]-a[n-1-m];for(in-1;im-1;i--){int ta[i]-a[i-m];if(tmax)maxt;}printf(%d\n,max);}
}
传统计算会超时利用前缀和来解题。
