1.問題描述
描述
一個數(shù)的序列bi，當b1 < b2 < ... < bS的時候，我們稱這個序列是上升的荔烧。對于給定的一個序列(a1, a2, ..., aN)，我們可以得到一些上升的子序列(ai1, ai2, ..., aiK)汽久，這里1 <= i1 < i2 < ... < iK <= N鹤竭。比如，對于序列(1, 7, 3, 5, 9, 4, 8)景醇，有它的一些上升子序列臀稚，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4三痰，比如子序列(1, 3, 5, 8).
你的任務(wù)烁涌，就是對于給定的序列，求出最長上升子序列的長度酒觅。
輸入
輸入的第一行是序列的長度N (1 <= N <= 1000)撮执。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000舷丹。
輸出
最長上升子序列的長度抒钱。
樣例輸入
7
1 7 3 5 9 4 8
樣例輸出
4
2.解題思路
此題用動態(tài)規(guī)劃來解決
第一種方法
1）找子問題
一個上升子序列中最右邊的那個數(shù)，稱為該子序列的“終點”颜凯。
即可轉(zhuǎn)化成：
“求以ak（k=1,2,3谋币，.....，N）為終點的最長上升子序列的長度”
雖然這個子問題和原問題形式上并不完全一樣症概，但是只要這N個子問題都解決了蕾额，那么這N個子問題的解中，最大的那個就是整個問題的解彼城。
2）確定狀態(tài)
子問題只和一個變量（數(shù)字的位置相關(guān)）诅蝶，因此序列中數(shù)的位置k就是“狀態(tài)”，而狀態(tài)k對應(yīng)的“值”募壕，就是以ak作為“終點”的最長上升子序列的長度调炬。
狀態(tài)一共有N個。
3）找出狀態(tài)轉(zhuǎn)移方程
maxLen（k）表示以ak作為“終點”的最長上升子序列的長度
maxLen（k）的值舱馅，就是在ak左邊缰泡，“終點”數(shù)值小于ak，且長度最大的那個上升子序列的長度再加1代嗤。因為ak左邊任何“終點”小于ak的子序列棘钞，加上ak后就能形成一個更長的子序列缠借。
程序如下：時間復雜度為O（N^2）
#include <iostream>
#define MaxSize 1001
using namespace std;
int MaxInArray(int * arr,int n);
int main(){
int n;
int MaxLen[MaxSize];//以i為終點的最長上升子序列的長度
int array[MaxSize];
cin >> n;
for(int i =1;i<=n;++i){
cin >> array[i];
MaxLen[i] = 1;//賦初值
}
for(int i=1;i<=n;++i)
//每次求以第i個數(shù)為終點的最長子序列的長度
for(int j =1;j<=i;++j)
//察看以第j個數(shù)為終點的最長上升子序列
if(array[i] > array[j])
MaxLen[i] = max(MaxLen[i],MaxLen[j]+1);
cout << MaxInArray(MaxLen,n);
return 0;
}
int MaxInArray(int *arr,int n){
int Max = arr[1];
for(int i=2;i<=n;++i)
if(Max < arr[i])
Max = arr[i];
return Max;
}
第二種方法(時間復雜度為O(nlogn))
后來在遇到一道LIS的題，用上面O(nlogn)的過不了宜猜，然后了解到下面這種解法：
我們定義一個最小的有序序列l(wèi)ens[]泼返，其長度為len。
用題目給的1 7 3 5 9 4 8來舉例宝恶。
我們定義一個數(shù)組a[7]={1,7,3,5,9,4,8}
a[1] = 1符隙，我們把1放進lens[1]趴捅，然后序列l(wèi)ens的長度len+1垫毙，len = 1
a[2] = 7,a[2]>lens[1]，我們把7放進lens[2]拱绑，然后序列l(wèi)ens的長度len+1综芥，len = 2
a[3] = 3,a[3]<lens[2]，因為序列l(wèi)ens存放的是最小的有序序列猎拨，所以我們把lens[2]替換成
a[3]膀藐，此時lens[2] = 3，因為此時只是替換红省，并沒有使lens變長额各，所以len不變
a[4] = 5,a[4]>lens[2]，我們把5放進lens[3]吧恃，然后序列l(wèi)ens的長度len+1虾啦，len = 3
a[5] = 9,a[5]>lens[3]，我們把9放進lens[4]痕寓，然后序列l(wèi)ens的長度len+1傲醉，len = 4
a[6] = 4,a[6]<lens[3],我們把lens[3]替換成a[6]，此時lens[3] = 4呻率，因為此時只是替換，并沒有使lens變長，所以len不變
a[7] = 8,a[7]<lens[4],我們把lens[4]替換成a[7]掖肋，此時lens[4] = 8会宪，因為此時只是替換，并沒有使lens變長元践，所以len不變
最終len為4挪丢，和我們所要求的長度結(jié)果是一致的，但是此時的有序序列不一定就是我們的最長上升子序列卢厂，此方法只能求長度乾蓬，但是不能用來求真正的最長上升子序列
經(jīng)過上面的例子，我們可以得出
如果a[i]>lens[len]慎恒，lens[++len] = a[i]
不然則從lens這有序序列中找出一個下界x（找到一個最大的x滿足len[x]<a[i]）任内，然后將lens[x]替換為a[i]撵渡，此時查找下界用二分查找，即可使整個算法的時間復雜度為O(nlogn)
改進版程序代碼：
#include <iostream>
using namespace std;
int arr[100000];
int search(int l,int r,int num,int a[]);
int LIS(int n);
int main(){
int n;
cin >> n;
for(int i=1;i<=n;++i)
cin >> arr[i];
cout << LIS(n) <<endl;
return 0;
}
int search(int l,int r,int num,int a[]){
int mid;
while(l<=r){
mid = (l+r)>>1;
if(a[mid]<=num)
l = mid+1;
else
r = mid - 1;
}
return l;
}
int LIS(int n){
int * lens = new int [n+1];
int len = 1;
lens[1] = arr[1];
for(int i = 2;i<=n;++i){
if(arr[i]>lens[len])
lens[++len] = arr[i];
else{
int p = search(1,len,arr[i],lens);
lens[p] = arr[i];
}
}
return len;
}
