點擊打開鏈接

就是尋找LIS 并打印出來

dp[i]表示到包括第i個數的前i個的最長遞增的長度

從數列從后往前找就好了 ，如果從前往后，前面的大數會覆蓋掉后面的小數，就不對了

代碼：

#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+10;int a[maxn],dp[maxn],ans[maxn];vector<int> v;int main(){	int t; cin>>t;	while(t--){		int n; cin >> n;		for(int i=1; i<=n; i++)			cin >> a[i];		memset(ans,0x3f,sizeof(ans));		memset(dp,0,sizeof(dp));		v.clear();		int mx = -1;		for(int i=1; i<=n; i++){			int p = lower_bound(ans+1,ans+1+n,a[i])-ans;			ans[p] = a[i];			dp[i] = p;			mx = max(mx,p);		}		cout << mx << endl;		int k = maxn;		for(int i=n; i>=1; i--){			if(dp[i]==mx && a[i]<k){				v.push_back(a[i]);				k = a[i];				mx--;			}		}		// int k = -1,cnt=1;		// for(int i=1; i<=n; i++){ // 不能正序，前面大的數會覆蓋后面小的數 不能達到最長		// 	if(dp[i]==cnt && a[i]>k){		// 		v.push_back(a[i]);		// 		k = a[i];		// 		cnt++;		// 	}		// }		for(int i=v.size()-1; i>=1; i--)			cout << v[i] << " ";		cout << v[0] << endl;	}}