tyvj无法登陆_tyvj_tyvj测试数据

2011.8.7 0:18

最大子序和是一道动态规划的题，但是从数据范围来看它没有那么简单，可以用RMQ来做，还可用单调队列来做。

先说一下单调队列。单调队列是指在队列中的元素是满足单调的性质的，单调增或减。并且在队列中的元素（以单调增为例），队尾往往是最小的，队头是最大的，并且对于这道题来说，队列中的元素都满足了不超过i-m的性质。

那么对于这道题来说，先预处理下数据,s[i]表示从头到i的所有元素和，那么要想要到i为结尾的最大子序和最大，是不是要用s[i]减去之前一个最小的一个s[k]，才使得s[i]-s[k]最大，那么利用单调队列的性质，用s[i]-q[head]一定是在不超过m的情况下数最大，因为q[head]一定是队列里中最小的。那么这就是对于当前找最大的操作。

维护单调队列的操作，需要开一个数组time[i]，记录队列中i的位置是在time[i]时被更新的，换句话说就是为了防止在查询时超过m。在这个单调队列里不仅元素单调，并且时间也单调，首先说下队头的作用（对于这道题来说）只是提取出队中最小值，它只会一直inc,不会dec。而队尾就不同了，它要掌管插入元素维护队单调的操作，当新来的元素小于队尾的时候，为了维护队列的单调性，队尾就会一直减小，知道找到一个不比新来的元素小的数，就把他插入进来，新队列由此产生，之前的元素被抛弃，这样就维护了队列的单调性。

还有一个细节要注意：在TYVJ上我AC的程序这组数据过不了：4 6

4 5 3 -4 2 -8

答案是12没错吧，但我的程序跑出8来，但是确实是AC程序。tyvj

因为没有考虑s[0]:=0;

当一个序列都是正数的时候，这些数一定都要对吧，但是s[i]-q[head]这时head=1，q[1]被初始化成s[1]，队中没有不取元素这种情况，所以我inc(n)了，s[1]:=0;q[1]:=s[1]=0 就避免了这种情况。所以要注意这种全都取和全都不取的极限情况。tyvj

代码：

var

q,time,s:Arr

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-35560-1.html