动态最大连续和

时间限制: C/C++/Pascal 1000 ms; Others 2000 ms

内存限制: 256 MB

题目描述:

Zeratul有一个数列a[1...n],最开始数列中的所有元素都为负无穷大。

接下来Zeratul要做m次操作,每次操作会把一个数改成一个非负整数。在每次操作之后,你要输出这个数列的最大连续和。所谓最大连续和,就是所有连续子序列a[L...R]的和的最大值。

输入格式:

第一行包括两个整数n,m,代表数列的长度和操作的次数。

接下来m行,每行包括两个整数pos,val,代表将a[pos]的值改为val。

输出格式:

输出m行,在每次操作之后输出这个数列的最大连续和。

样例:

Input
Copy
5 5
1 5
2 4
3 3
5 100
4 5
Output
Copy
5
9
12
100
117

数据范围及提示

【输入输出样例的解释】

第一次操作之后,数列为5 -INF -INF -INF -INF,最大连续和是5;

第二次操作之后,数列为5 4 -INF -INF -INF,最大连续和是9;

第三次操作之后,数列为5 4 3 -INF -INF,最大连续和是12;

第四次操作之后,数列为5 4 3 -INF 100,最大连续和是100;

第五次操作之后,数列为5 4 3 5 100,最大连续和是117。

对于30%的数据,n,m<=100。

对于50%的数据,n,m<=1000。

对于70%的数据,所有的pos不会重复,即每次操作前a[pos]的值都为负无穷大。

对于100%的数据,n,m<=100000,0<=val<=100000,1<=pos<=n

2 人解决,7 人已尝试。

3 份提交通过,共有 9 份提交。

公开: Zeratul

来源: Zeratul

题目信息

题目类型:传统题

文件IO

输入文件名:sum.in

输出文件名:sum.out

AMAZE UI
Hello world!