xtu oj 1169 最大子段和

本文主要是介绍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);}
}

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

这篇关于xtu oj 1169 最大子段和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---