> 假若把这数列分成两段，1，5是其中一段，2，3，4是其中一段，这就能得出结果了。有什么好方法呢？我想到用数组保存其中一段为最小值1，最大值5，的数列，而另一个为最小值2，最大值4的段，这样就能解决了。就是说当读到一个数时，判断下这个数是否比当前所记录的段中的最大值要大，是的话，就会形成一个新的更长的段，如果不是，则另开新段，把这个数记为最小值，最大值设为和最小值相等，这样就肯定对的。
>     现在问题算是初步解决了。但是还有个严重的问题，就是时限，如果每读入一个数，都与每个记录段作比较的话，这样会达到O(n^2)的，对于这题规模绝对过不了。这样就开始着手想优化。利用上面的例子，记录一段为{1，5}，另一段为{2，4}，联想下是不是可以像最长上升子序列那样用二分把复杂度降为 O(nlogn)呢？假设现在读到一个6，则可以把{1，5}段扩长为{1，6}，{2，4}段也扩长为{2，6}，但2出现在1后，所以{1，6}段肯定比{2，6}段长，而{2，6}段也没必要保留，因为如果读到在{2，6}段中间的数，中间因为出现一个6，对于条件不成立；若读到大于6的数，则可以扩展{2，6}段时{1，6}段同样可以扩展。而当只读了1，5时，存在段{1，5}后，若读到一个3，需要另开新段{3，3}，此时若读到6，则依上扩展成段{1，6}，并舍弃{3，3}段；若读到一个4，则{1，5}段不可扩展，只能把{3，3}段扩成{3，4}段；若读到一个2，则需要另开新段 {2，2}，同时由于{3，3}段后面出现了比最小值更小的数，这段不再保留，只剩下{1，5}和{2，2}。通过简单的例子，大概可以看出保存的最小值是递增的，而保存的最大值是递减的，同时由于当修改某段后，此段以外的段不用修改，因此可以保持很好的性质，可以用二分完成，每输入一个数，先查找最大值，若小于所有的最大值，则需要添加新段，再来查找最小值。这样就可以成功地求出最长距离的满足题目要求的段了。
>     写好代码，其实也不长，就1k左右，

• Re:路径压缩 (0) v85216192 2011-05-01 22:44:32