# POJ 2533 最长上升子序列
[POJ-2533](http://poj.org/problem?id=2533)
## 题目分析
最长上升子序列, 裸题.
题意描述不清, 还以为是上升下降都要算然后取最长的呢...
## 代码(C++)
## dp方法
相当野蛮的线性遍历套逆序遍历(对每一个数查找可以接上的接得最长的数). $O(n^2)$.
```c++
#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;
int main(){
int n, a[1005], dp[1005], maxn = -1;
fill(dp, dp+1005, 1);
fill(a, a+1005, 0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(a[j] < a[i])
dp[i] = max(dp[i], dp[j]+1);
}
if(dp[i] > maxn)
maxn = dp[i];
}
cout << maxn << endl;
return 0;
}
```
## 最大放置法
很神奇的方法, 不看不知道一看吓一跳. $O(n*log(n))$.
```
#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;
int main(){
int n, a[1005], dp[1005], maxn = -1;
fill(dp, dp+1005, 1);
fill(a, a+1005, 0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
fill(dp, dp+1005, INF);
for(int i = 0; i < n; i++){
*lower_bound(dp, dp+n, a[i]) = a[i];
}
cout << lower_bound(dp, dp+n, INF) - dp << endl;
return 0;
}
```
![]()