LIS

素颜马尾好姑娘i 2021-11-09 15:36 285阅读 0赞

### LIS ###

*  通过LCS求解
 *  直接dp
 *  O(nlogn)优化

# 通过LCS求解 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    
    /* LIS求解最长递增子序列 通过LCS的思想求解 时间复杂度为O(n^2) */
    
    int LIS(int a[],int n){ 
    	int b[maxn];
    	for(int i=0;i<n;i++)b[i]=a[i];
    	int dp[maxn][maxn]={ 0};
    	sort(b,b+n);
    	for(int i=1;i<=n;i++){ 
    		for(int j=1;j<=n;j++){ 
    			if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1;
    			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    		}
    	}
    	return dp[n][n];
    }
    
    int main(){ 
    	int a[maxn],n;
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
        cout<<LIS(a,n)<<endl;
    }

# 直接dp #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    
    /* LIS求解最长递增子序列 dp[i]=max(dp[j],0)+1;j<i,a[j]<a[i] dp[i]表示已i结尾时的最长递增子序列的长度 时间复杂度为O(n^2) */
    
    int LIS(int a[],int n){ 
    	int dp[maxn]={ 1},m=0,ans=0;//dp[0]=1;第一个肯定是一个递增子序列并且长度为1
    	for(int i=1;i<n;i++){ 
    		m = 0;
    		for(int j=0;j<i;j++)if(dp[j]>m&&a[i]>a[j])m=dp[j];
    		dp[i]=m+1;
    		ans = max(ans,dp[i]);
    	}
    	return ans;
    }
    
    int main(){ 
    	int a[maxn],n;
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
        cout<<LIS(a,n)<<endl;
    }

# O(nlogn)优化 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    
    /* LIS求解最长递增子序列 通过序列本身的特征求解，通过一个辅助数组d[]统计最长子序列的长度 */
    
    int LIS(int a[],int n){ 
    	int d[maxn]={ 0},len=0;
    	d[len++]=a[0];//初始化，
    	for(int i=1;i<n;i++){ 
    		if(a[i]>d[len-1]){ 
    			d[len++]=a[i];
    		}//大于辅助数组的最后一个元素，将其加入d[]的最后面
    		else{ 
    			int pos = lower_bound(d,d+len,a[i])-d;//如果小于的话就更新d[],替换出第一个大于它的数
    			/* 为了使递增子序列越长，前面元素越小越易使得后面的元素容易添加到子序列后面 而通过该操作不影响子序列的长度 lower_bound()是STL查找一个顺序序列的一个函数，返回的是第一个大于或者等于查找数的位置，由于返回的是地址 需要减去首地址 */
    			d[pos]=a[i];
    		}
    	}
    	return len;
    }
    
    int main(){ 
    	int a[maxn],n;
    	cin>>n;
    	for(int i=0;i<n;i++)cin>>a[i];
    	cout<<LIS(a,n)<<endl;
    }