有两种算法复杂度为O(n*logn)和O(n^2)
O(n^2)算法分析如下: (a[1]...a[n] 存的都是输入的数)
1、对于a[n]来说,由于它是最后一个数,所以当从a[n]开始查找时,只存在长度为1的不下降子序列;
2、若从a[n-1]开始查找,则存在下面的两种可能性:
(1)若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n].
(2)若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。
3、一般若从a[t]开始,此时最长不下降子序列应该是按下列方法求出的:
在a[t+1],a[t+2],...a[n]中,找出一个比a[t]大的且最长的不下降......
阅读全文