xtu oj 1169 最大子段和

题目描述

给你一个数列a1,a2,...,an,求m个连续数字组成的子段和最大值。

输入

有多个样例，每个样例的第一行是两个整数n和m，(1≤m≤n;≤100,000)。如果n和m为0表示输入结束，这个样例不需要处理。第二行是n个整数ai，0≤ai≤10000。

输出

每行输出一个整数，即样例的结果。

样例输入

6 3
1 2 3 4 5 6
6 3 
1 2 3 3 2 1
0 0

样例输出

15
8

AC代码

#include<stdio.h>
#define N 100005
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(m==0&&n==0)break;
		int a[N]={};
		int i,j;
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		for(i=0;i<n;i++){
		   a[i]+=a[i-1];
		}
		int max=a[n-1]-a[n-1-m];
		for(i=n-1;i>=m-1;i--){
			int t=a[i]-a[i-m];
			if(t>=max)max=t;
		}
		printf("%d\n",max);
	}
}

传统计算会超时，利用前缀和来解题。