poj2533:最長上升子序列
好久沒更博客了，最近又是要准備poj考試，看到了這道題，記得算法設計與分析課上有講過，但是一直想不起最優的做法，搞了好久，最後看了看數據規模就用傻逼方法A了。
復制代碼
總時間限制: 2000ms 內存限制: 65536kB
描述
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
輸入
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
輸出
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
樣例輸入
7
1 7 3 5 9 4 8
樣例輸出
4
來源
Northeastern Europe 2002, Far-Eastern Subregion
復制代碼
最優的做法應該是這樣的：
核心思想是要維護一個遞增序列，每訪問到一個數據的時候，可以通過這個遞增序列查到當前比自己小的數據能夠組成的上升序列最長為多少。具體做法： 初始的時候，遞增鏈表為空，從頭開始遍歷該數組，將第一個數字加入到鏈表中，然後繼續訪問，當訪問到的數字比當前鏈表末尾數字還大的時候，將該數字添加到鏈表中，當訪問到的數字比當前鏈表的末尾數字要小的時候，則反向查詢該鏈表，直到找到第一個比訪問到的數字要小的數字時，將訪問到的數字替換掉鏈表中查詢到的數字的下一個數字。遍歷完整個數組之後，鏈表的長度即為該數組的最長上升子序列的長度。時間復雜度為O(nk),k為鏈表的長度。
當然我看到有人的具體做法是用數組來維護這個遞增序列，而不是鏈表，而因為這個數組是遞增的，所以每次查詢的時候可以用二分查找來做，那樣的話時間復雜度為O(nlogk)，有興趣可以看這篇博客，裡面介紹得很清楚，還有例子！
我的弱B代碼貼在下面，大家看看就好 0 0
復制代碼
#include <iostream>
using namespace std;
int a[1001]={0};
int len[1001]={0};
int main()
{
int n;
while(cin>>n){
len[0] = 1;
for(int i = 0; i < n; i ++){
cin>>a[i];
int m = 0;
for(int j = 0; j < i; j ++)
{
if(m < len[j] && a[j] < a[i]){
m = len[j];
}
}
len[i] = m+1;
}
int m = 0;
for(int i = 0; i < n; i ++)
{
if(m < len[i])
m = len[i];
}
cout<<m<<endl;
}
return 0;
}
