http://acm.pku.edu.cn/JudgeOnline/problem?id=1631
这个题目可以转化为最长上升子序列,这样这个题目似乎就和2533 Longest Ordered Subsequence 1887 Testing the CATCHER一样了,迅速写下代码,结果超时!看来只能用O(nlogn)的算法了。
在O(n^2)的算法中:创建一个一维数组array[j],opt[],array[j]表示序列的元素,opt[i]表示以第i个元素结尾的序列中的最长下降子序列,初始化为1,对于一个opt[i],遍历前面的每个元素j,如果array[j]>array[i]且opt[j]>=opt[i],那么opt[j]就要加1,在这里,遍历前面的每个元素j,寻找此前最大的子序列时间复杂度为O(n),如果我们在一个有序的序列中查找此前最大的序列长度,我们就可以用二分查找,时间复杂度就会降为O(logn),总的时间复杂度就会为O(nlogn)。为此,我们增加一个一维数组B,B[i]表示当前序列为i的末尾元素的最小值。例如对于序列:4 2 6 3 1 5 :
i |
1 |
2 |
3 |
4 |
5 |
6 |
array |
4 |
2 |
6 |
3 |
1 |
5 |
opt |
1 |
1 |
2 |
2 |
1 |
3 |
B |
1 |
3 |
5 |
|
|
|
构建过程如下:
i=1时,opt[i]=1 B[i]=4(当前为1的序列的末尾元素的最小值)
opt |
1 |
1 |
1 |
1 |
1 |
1 |
B |
4 |
|
|
|
|
|
i=2时,2不大于4,所以opt[i]=1,将B[1]更新为2
opt |
1 |
1 |
1 |
1 |
1 |
1 |
B |
2 |
|
|
|
|
|
i=3时,6大于2,所以opt[i]=1+1,将B[2]更新为6
opt |
1 |
1 |
2 |
1 |
1 |
1 |
B |
2 |
6 |
|
|
|
|
i=4时,3在2 6之间,所以opt[i]=1+1,将B[2]更新为3
opt |
1 |
1 |
2 |
2 |
1 |
1 |
B |
2 |
3 |
|
|
|
|
i=5时,1小于2,所以opt[i]=1,将B[1]更新为1
opt |
1 |
1 |
2 |
2 |
1 |
1 |
|