Cod sursa(job #1213368)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 27 iulie 2014 22:32:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<algorithm>
#include<stack>
using namespace std;
#define LL long long
#define MAXN 100005
stack<LL> st;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
LL N,A[MAXN],best[MAXN],pre[MAXN],maxim,p;
int main() {
	int i,j;
	cin>>N;
	for(i=1;i<=N;i++)
	             cin>>A[i];
	maxim=1;             
	for(i=1;i<=N;i++) { 
     best[i]=1,pre[i]=-1; 
	 for(j=1;j<=i-1;j++)
	           if(A[j]<A[i] && best[j]+1>best[i]){
			                          best[i]=best[j]+1;
									  pre[i]=j;
								if(best[i]>maxim) maxim=best[i],p=i;	    
										 }               
    }
	cout<<maxim<<"\n";
	 i=p; 
	 while(i!=-1)
	    st.push(A[i]),i=pre[i];
	while(st.size()>0)
	         cout<<st.top()<<" ",st.pop();	 
return 0;
}