最长上升子序列

子序列：一段序列中选取一些位置递增（或递减）的元素作为子序列，如 {1,2,3,4,5,6,7,8,9}这一段序列，可以选取{1,3,5,8,9}作为子序列，也可以选取{1,2,4,7}作为子序列。

最长上升子序列：子序列中的所有元素都是递增的，并且要求该段上升子序列，在所有的上升子序列中长度是最长的。

我们想要求取一段序列的最长上升子序列，一般会有两种方法，一种是动态规划（DP），另一种是二分查找。

先来讲动态规划怎么完成这个问题。

众所周知，动态规划是将我们要解决的问题分为若干个子问题，这些子问题与原问题有着相同的性质和求解方式，也就是可以通过局部最优解推广到全局最优解，我们仔细看看这个问题，发现长度为n的最长上升子序列是可以由长度为n-1的上升子序列推出的，也就是可以通过使用动态规划来解决这个问题。具体代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e3+9;
int dp[maxn],a[maxn];
int main(){
	int i,j,k,n;
	cin>>n;int len=1;
	for(i=1;i<=n;i++){
		cin>>a[i];dp[i]=1;
		for(j=1;j<i;j++)
			if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
		if(dp[i]>len)len=dp[i];
	}
	cout<<len<<endl;
}

仔细观察代码，我们能够发现若是使用动态规划的话时间复杂度为O(n*n),对于较大的数据量就不适用了，这个时候我们就需要用到第二种方法了。

二分查找维护最长上升子序列

这种方法较动态规划而言不易理解一点，所以我会讲更详细一点。假如给出一段序列{4,2,1,5,4,9,3}，求最长上升子序列。

我们首先需要开两个数组，a数组用来储存给出的序列，b数组用来储存最长上升子序列（不是真正的最长上升子序列），然后遍历整个a数组

首先找到4,b[1]=4,len=1

再找到2,发现2比b数组里的所有元素都小，更新b[1]=2，len=1

接着我们找到1,发现1比b数组里的所有元素都小，更新b[1]=1,len=1

到5,发现5比b数组里所有元素都大，b[2]=5,len=2

到3,发现b数组里5是比3大的最小数字，找到5的位置，b[2]=3,len=2

到9,发现9比b数组里所有元素都大，b[3]=9,len=3

到8,发现b数组里4是比3大的最小数字，找到9的位置，b[2]=3,len=3

通过这样的操作后，我们得到了最长上升子序列的长度。我们很容易就能发现，在这些操作当中，最关键的一部分就是查找了，查找的方法直接决定了整个算法的时间复杂度，如果我们通过遍历整个b数组来查找的话，整个算法的时间复杂度就是O(n*n),与动态规划没有什么区别，但是若我们使用二分查找的话，就能把算法时间复杂度降到O(nlogn)。可能有些人不知道为什么类似于最后一步的操作有什么意义，其实我们通过这种操作的来的最长上升子序列不是真正的最长上升子序列，我们的目的只是求出最长上升子序列的长度，假如我再在这个序列后面加上4和5的话，那么b[3]=4,b[4]=5,len=3，但是如果我不进行最后一步那样的操作的话,那么就是b[3]=5,len=3，我们得到的长度就明显比最长上升子序列的长度少1，这不符合我们的初衷。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f;
typedef long long LL;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int find(int l,int r,int val){
	int ans=1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]>=val){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return l;
}
int main(){
	int i,j,k,n,len=0;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
		int next=find(1,len,a[i]);
		b[next]=a[i];
		if(next>len)len=next;
	}
	cout<<len<<endl;
}

上述代码实现的是最长严格上升子序列，若是想实现最长不递减子序列的话，我们则需要将find函数里面的b[mid]>=val改为b[mid]>val。也就是对于最长严格上升子序列来说，我们需要找到b数组里第一个大于等于a[i]的数并替换(若b数组里有与a[i]相等的数而不去替换的话，则会导致b数组里面有两个相等的数，可能导致所求长度错误)，对于最长非递减子序列来说，我们则需要找到b数组里第一个大于a[i]的数并替换。

最长上升子序列

推荐阅读