問(wèn)題描述
??給定n個(gè)數(shù)字的序列扶平，如11赋荆，3琳水，6拆讯，9，13拗引，14，18，12妈踊，15，2泪漂，16廊营，20，8萝勤，19露筒，問(wèn)最長(zhǎng)的上升序列長(zhǎng)度是多少。
??上升序列敌卓，分為嚴(yán)格單調(diào)遞增序列和單調(diào)不減序列慎式。前者需滿足序列L中，i<j假哎，L[i]<L[j]瞬捕，而后者可取等號(hào)。例如舵抹，上述序列中存在一個(gè)遞增序列{3肪虎，8，19}惧蛹，顯然不是最長(zhǎng)的上升子序列扇救。
分析
??因?yàn)檫f增的判斷是在原序列末尾元素基礎(chǔ)上進(jìn)行比較的，是動(dòng)態(tài)規(guī)劃典例香嗓。遞推關(guān)系如下：
??對(duì)于每個(gè)元素s[i]迅腔，向前找所有小于s[i]的元素。
- 若存在s[j]<s[i]（j<i）靠娱，則dp[i] = max{dp[j]} + 1
- 若不存在s[j]<s[i]（j<i）,則s[i]自身構(gòu)成一個(gè)子序列沧烈，dp[i] = max{dp[k]}，k為小于i的整數(shù)
可以得出
dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=4, dp[6]=5, dp[7]=6, dp[8]=6, dp[9]=6, dp[10]=6, dp[11]=7, dp[12]=8, dp[13]=8, dp[14]=8
代碼實(shí)現(xiàn)
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
int s[maxn], dp[maxn];
int main()
{
int n; cin >> n;
for(int i=0;i<n;i++) cin >> s[i];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int i;
for(i=1;i<n;i++){
int tem_max=0;
for(int j=0;j<i;j++){
if(s[j]<s[i]) tem_max = max(tem_max, dp[j]);
}
dp[i] = tem_max+1;
}
cout << dp[n-1];
return 0;
}
??上面代碼的復(fù)雜度為O(n^n)像云，每次考慮一個(gè)元素都需要和它之前的數(shù)依次比較一遍锌雀，比較笨。我們思考是否可以用一個(gè)數(shù)組保存當(dāng)前最佳的最長(zhǎng)子序列迅诬，這樣每次新加入一個(gè)數(shù)腋逆，只需將其與數(shù)組最后一個(gè)元素比較即可。
??這會(huì)引入一個(gè)問(wèn)題侈贷，保存的最長(zhǎng)上升子序列的數(shù)組是動(dòng)態(tài)變化的惩歉，并且為貪心使盡可能更多的元素加入，需要不斷修改數(shù)組元素為不改變大小關(guān)系的最小值。
??例如撑蚌，已有當(dāng)前的最長(zhǎng)子序列{3上遥，6，9争涌，13露该，14，18}第煮，當(dāng)遇到12時(shí)解幼，比較18>12，那么尋找數(shù)組中第一個(gè)大于12的元素將其替換包警。處理完12得到的子序列是{3撵摆，6，9害晦，12特铝，14，18}壹瘟，長(zhǎng)度不變鲫剿，需要特別注意的是，此序列不能代表真實(shí)的最長(zhǎng)上升子序列稻轨，只是為求解序列長(zhǎng)度提供的一種量化方法灵莲。
??將復(fù)雜度降到O(nlgn)，代碼如下
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
int s[maxn], lis[maxn];
int bi_search(int A[], int right, int left, int num){ //二分查找遞增數(shù)列a[n]中第一個(gè)大于num的元素下標(biāo)殴俱，并返回
int mid;
while(right<left){
mid = (right+left)/2;
if(num<=A[mid]) left = mid;
else right = mid+1;
}
return left;
}
int main()
{
int n; cin >> n;
int maxl;
for(int i=0;i<n;i++) cin >> s[i];
memset(lis, 0, sizeof(lis));
lis[0] = s[0]; maxl = 1; //maxl表示lis數(shù)組元素個(gè)數(shù)政冻，即最長(zhǎng)上升子序列長(zhǎng)度
for(int i=1;i<n;i++){
if(lis[maxl-1]<s[i])
lis[maxl++] = s[i];
else if(lis[maxl-1]==s[i]) continue;
else{
int p = bi_search(lis, 0, maxl-1, s[i]);
lis[p] = s[i];
}
}
cout << maxl;
return 0;
}
注意
??上面兩個(gè)算法都不能直接求出最長(zhǎng)上升子序列
