tzoj 6315 求最长不下降序列

描述

设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)若存在i1<i2<i3<…<ie且有b(i1)≤b(i2)≤…≤b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。 例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

输入

第一行为n, 第二行为用空格隔开的n个整数。

输出

第一行为输出最大个数； 第二行为max个整数形成的不下降序列，答案可能不唯一，输出一种就可以了，本题进行特殊评测。

样例输入

14

13 7 9 16 38 24 37 18 44 19 21 22 63 15

样例输出

8

7 9 16 18 19 21 22 63

一道较为典型的dp题 困扰我的还是输出每个数据（第二行） 先给出代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn] ;
int dp[maxn];///dp[i]在i前比a[i]小的个数
map<int,int> mp;///记录该数前一个数的下标
int n; 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)dp[i]=1;
	int ans=1;
	int maxx=1;
	for(int i=2 ;i<=n ;++i ){
       	for(int j=i-1;j>=1;--j){
       		//cout<<"i: "<<i<<"j: "<<j<<"\n";
       		 if(a[j]<=a[i]){
       		 	if(dp[i]<dp[j]+1)
       		 	    {
       		 	    	mp[i]=j;
       		 	    	dp[i]=dp[j]+1;
						//cout<<i<<" "<<j<<endl;
       		 	    }
       		 	    if(dp[i]>ans){
       		 	    	
       		 	    	ans=dp[i];
       		            maxx=i;
						break;
					}
				}
		   }
	}
	//for(int i=1;i<=n;++i)cout<<dp[i]<<" ";
    cout<<ans<<"\n";
    stack<int> st;
    st.push(a[maxx]);
    int tmp=mp[maxx];
	while(tmp){
		st.push(a[tmp]);
		tmp=mp[tmp];
	} 
	bool flag=true;
	while(!st.empty()){
		if(flag)cout<<st.top();
		else cout<<" "<<st.top();
		st.pop();
		flag=false;
	}
	return 0;
}

该代码多用了栈，耗费了时间和空间 我觉得我的代码还可以再优化一下mp反向记录就行，然后找到第一个数字的下标，就不用遇到栈，或者直接反向读取数据，然后判断不上升序列就行