最长上升子序列(LIS)

题目链接
dp数组：dp[maxn]；存储数组: a[N];
求一个长度为N的上升子序列的递推公式：
1.dp[i] : 定义为以a[i]为结尾的(数组下标从 0 开始)序列最大上升子序列的值
2.以a[i]为结尾的最大上升子序列为：
（1）a[i] 本身
（2）j < i && a[j]<a[i]以a[j]为结尾的上升子序列,末尾追加a[i]的子序列
由此得出递推公式
dp[i] = max(1,dp[j] +1 | （ j < i && a[i] < a[j] ） );

O(n^2)算法

int n;
int dp[maxn],a[N];
void solve()
{
	int res = 0;
	for( int i = 0; i < n; i++ )
	{
		dp[i] = 1;
		for( int j = 0; j < i; j++ )
		{
			if(a[j] < a[i])
			dp[i] = max( dp[i], dp[j] + 1 );
		}
		res = max(res,dp[i]);
	}
	cout<<ans<<endl;
}

O(nlog(n))算法
思考：
前面我们利用DP求取针对最末位的元素的最长的子序列。如果子序列的长度相同，那么最末位的元素较小的在之后会更加有优势，所以我们再反过来用DP针对相同长度情况下最小的末尾元素进行求解。

dp[i] : 长度为i+1的上升子序列中末尾元素的最小值（不存在的话就是INF)

我们来看看如何用DP来更新这个数组。
对序列：4 2 3 1 5

1. 最开始全部dp[i]的值都初始化为INF.
2. 然后由前到后逐个考虑数组的元素，对于每个aj,如果i=0或者dp[i-1]<a;的话，就用dp[i]=min(dp[i],a)进行更新。
3. 最终找出使得dp[i]<INF的最大的i+1就是结果了。
   这个DP直接实现的话，能够与前面的方法一样在O(n2)的时间内给出结果，但这一算法还可以进一步优化。首先dp数组中除INF之外是单调递增的，所以可以知道对于每个a;最多只需要1次更新。对于这次更新究竟应该在什么位置，不必逐个遍历，可以利用二分搜索，这样就可以在O(nlogn)时间内求出结果。

const int N = 1e6;
const int INF = (1<<30)-1;
int a[N], dp[N], n;
void solve()
{
	fill(dp,dp+n,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; 
} 

题目链接参考代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6;
const int INF = (1<<30)-1;
int n,dp[N],map[N],a[N],b[N];
void solve()
{
	fill(dp,dp+n,INF);
	for(int i = 0;i<n;i++)
	{
		*lower_bound(dp,dp+n,b[i]) = b[i];
	} 
	cout<<lower_bound(dp,dp+n,INF) - dp<<endl; 
}
int main()
{
	int k;
	cin>>n;
	for(int i = 0;i<n;i++)
	{
		cin>>a[i];
		map[a[i]] = i;
	}
	for(int i = 0;i<n;i++)
	{
		cin>>k;
		b[i] = map[k];
	}
	solve();
}