题面
Description
给出一个 1 ∼ n (n ≤ 10^5) 的排列 P
求其最长上升子序列长度
Input
第一行一个正整数n，表示序列中整数个数；
第二行是空格隔开的n个整数组成的序列。
Output
最长上升子序列的长度
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
题解
分析LIS的两种做法
第一种：
最朴素的DP方法，时间复杂度为O(n^2)
状态：f[i]表示以ai结尾的最长LIS的长度
转移：f[i]=max{f[k]+1}(ak < ai)
代码：
void work()//DP解法,时间复杂度O(n^2)
{
f[1]=1;
for(int i=1;i<=N;++i)
a[i]=read();
for(int i=2;i<=N;++i)
for(int j=1;j<i;++j)
if(a[i]>a[j])
Ans=max(Ans,f[i]=f[j]+1);
printf("%d
",Ans);
}
第二种
观察题目，有一个条件：排列P
意味着并没有重复的数字
考虑到只需要求出最长LIS的长度
可以考虑去维护一个LIS
每次读入一个数字之后
如果大于当前的队尾，那么这个数可以更行LIS的长度
否则，找到比他大的数字中最小的那个，替换
这么做的理由是：如果两个数都能够放在LIS的某一位置，放更小的数一定比放更大的数更好。
那么，一边读入，一遍二分查找更新位置，时间复杂度O(nlogn)
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 100100
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int a[MAX];
int N,Ans=0;
//int f[MAX];
/*void work()//DP解法,时间复杂度O(n^2)
{
f[1]=1;
for(int i=1;i<=N;++i)
a[i]=read();
for(int i=2;i<=N;++i)
for(int j=1;j<i;++j)
if(a[i]>a[j])
Ans=max(Ans,f[i]=f[j]+1);
printf("%d
",Ans);
}*/
void Work()//正解,使用二分查找(保证了无重复数字)
{
//维护以i结束的LIS的长度
//维护排列P中，Pi的最小值，每次二分查找更新即可
int x;
vector<int> f;
f.push_back(read());//提前读取一个数
for(int i=2;i<=N;++i)
{
x=read();
if(x>f[f.size()-1])//如果比当前的LIS的最后一位要大，直接增加Ans
f.push_back(x);
else//否则找到一个满足条件的位置，直接替换
*lower_bound(f.begin(),f.end(),x)=x;
}
printf("%d
",f.size());
}
int main()
{
N=read();
//work();//O(n^2)的DP解法
Work();
return 0;
}