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