這個題相當經典。很多題目都可以等價過來。
一、簡單的O（n^2)的算法
很容易想到用動態規劃做。設lis[]用于保存第1~i元素元素中最長不下降序列的長度，則lis[i]=max(lis[j])+1,且num[i]>num[j],i>j。然后在lis[]中找到最大的一個值，時間復雜度是O(n^2)。
int
Longest_Increasing(
int
num[],
int
n){
int
lis[n],i,j;
for
(i=
0
;i<n;i++
){
lis[i]
=
1
;
for
(j=
0
;j<i;j++
)
if
(num[i]>num[j]&&lis[j]+
1
>
lis[i])
lis[i]
=lis[j]+
1
;
}
int
maxn=
0
;
for
(i=
0
;i<n;i++)
if
(maxn<lis[i]) maxn=
lis[i];
return
maxn;
}
二、復雜點的O(nlogn)算法
概述：O(nlogn)的算法關鍵是它建立了一個數組b[]，b[i]表示長度為i的不下降序列中結尾元素的最小值，用K表示數組目前的長度，算法完成后K的值即為最長不下降子序列的長度。
具體點來講：
設當前的以求出的長度為K，則判斷a[i]和b[k]：
1.如果a[i]>=b[k]，即a[i]大于長度為K的序列中的最后一個元素，這樣就可以使序列的長度增加1，即K=K+1,然后現在的b[k]=a[i]；
2.如果a[i]<b[k]，那么就在b[1]...b[k]中找到最大的j,使得b[j]<a[i],然后因為b[j]<a[i]，所以a[i]大于長度為j的序列的最后一個元素，那么就可以更新長度為j+1的序列的最后一個元素，即b[j+1]=a[i]。
算法復雜度的分析：
因為共有n個元素要進行計算；每次計算又要查找n次，所以復雜度是O(n^2)，但是，注意到b[]數組里的元素的單調遞增的，所以我們可以用二分法，查找變成了logn次。這樣算法的復雜度就變成了O(nlogn)。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
