最长递增子序列的三种解法（LIS）

1.用LCS(求LIS) 时间复杂度O(n^2)

思路：将原序列a排序后产生一个新的序列b，比较a和b最长公共子序 结果就是LIS.

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int dp[2][N];//滚动数组优化 
string a,b;
int LCS(){	
	int la=a.size(),lb=b.size();
	for(int i=1;i<=la;i++)
		for(int j=1;j<=lb;j++)
			if(a[i-1]==b[j-1])//如果相等直接加1 
				dp[i%2][j]=dp[(i-1)%2][j-1]+1;
			else dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]);//否则比较一下 
	return dp[la%2][lb]; 
}
int main(){
	cin>>a;
	b=a;
	sort(b.begin(),b.end());//b为排好序递增序列 
	cout<<LCS()<<endl;
	return 0; 
}

2.DP(时间复杂度 O(n^2)

思路：设dp[ i ] 为以a[i] 结尾的最长递增子序列， 对每个 i j从 1 到 i-1 遍历 找到最大值。
即 dp [ i ] = max( dp[ j ] , 0 ) +1 . 详情见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int dp[N],a[N],ans=1,n;//dp[i]表示以第i个数结尾的LIS的长度 
int lis(){  //时间复杂度O（n^2) 
	dp[1]=1;//初始化 
	for(int i=2;i<=n;i++)
	{
		int mx=0;//每次都为0 
		for(int j=1;j<i;j++)
			if(a[j]<a[i]&&dp[j]>mx)//如果a[j]<a[i]且dp[j]>mx 更新mx 
				mx=dp[j];
			dp[i]=mx+1;//更新dp[i] 
		ans=max(ans,dp[i]);//得到ans 
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<lis()<<endl;
	return 0;
}

3.辅助数组模拟.时间复杂度O(nlogn)

思路：用一个辅助数组保存LIS的每个数。对辅助数组的数进行两种操作，一：如果大于末尾的数直接添加，二：找到数组中第一个大于它的数进行替换。详情见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5; 
int a[N],d[N],n; //d[i]保存LIS的数字 
int  LIS(){
	int l=1;// l表示d[i]的长度 
	d[1]=a[1];//初始化 
	for(int i=2;i<=n;i++)
	{
		if(a[i]>d[l]) //如果大于d[l] 直接添加的末尾 
			d[++l]=a[i];
		else { //否则查找第一个大于a[i]的数 替换掉 
			int p=lower_bound(d+1,d+l+1,a[i])-d; //该数位置 复杂度 logn 
			d[p]=a[i];
		}
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<LIS()<<endl;
	return 0;
}

练习题。

1.导弹拦截

题目传送门本题是利用C++STL的查找功能 求LIS的裸题 复杂度 O（nlogn)
详情见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],d1[N],d2[N],l1,l2,k;//d2[i]保存 最长不增子序列 d1[i]保存 LIS(严格递增) 
void fun(){
	l1=l2=1;
	d1[1]=d2[1]=a[1];
	for(int i=2;i<k;i++)
	{
		if(a[i]>d1[l1]) //这里必须是大于，不然两个数可以合并为一个拦截系统。 
			d1[++l1]=a[i];
		else {
			 int p=lower_bound(d1+1,d1+l1+1,a[i])-d1;
			 d1[p]=a[i];
		}
		if(a[i]<=d2[l2])
			d2[++l2]=a[i];
		else {   //因为查找第一个‘小于’ 而不是小于等于 所以要用upper_bound 
			 int p=upper_bound(d2+1,d2+l2+1,a[i],greater<int>())-d2; //从左到右找到第一个小于a[i]的数. 
			 d2[p]=a[i];
		}
	}
}
int main(){
	k=1;
	while(cin>>a[k]) k++; //这里不能debug了只能到文件结束才会有输出 
	fun();
	printf("%d %d\n",l2,l1);
	return 0;
}