<题目链接>
题目大意：
裸的DP最长上升子序列，给你一段序列，求其最长上升子序列的长度，n^2的dp朴素算法过不了，这里用的是nlogn的算法，用了二分查找。
O(nlogn)算法
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N= 1e5+;
int a[N],rise[N]; int main(){
int n;while(~scanf("%d",&n)){
memset(rise,,sizeof(rise));
for(int i=;i<n;i++)scanf("%d",&a[i]);
int len=;
rise[]=-1e9;
for(int i=;i<n;i++){
if(a[i]>rise[len])rise[++len]=a[i];
else{
int j=lower_bound(rise+,rise++len,a[i])-rise;
rise[j]=a[i];
}
}
printf("%d\n",len);
}
}
虽然(n^2)算法过不了此题，但是还是先记录下
#include<cstdio>
int main()
{
int i, j, n;
int dp[], a[];
while (scanf("%d", &n) != EOF)
{
int max = ;
for (i = ; i<n; i++)
scanf("%d", &a[i]);
dp[] = ;
for (i = ; i<n; i++)
{
dp[i] = ;
for (j = ; j<i; j++)
if (a[j]<a[i] && dp[j] + >dp[i])
dp[i] = dp[j] + ;
}
for (i = ; i<n; i++)
if (max<dp[i])
max = dp[i];
printf("%d\n", max);
}
}