Cod sursa(job #2306414)

Utilizator Rares31100Popa Rares Rares31100 Data 22 decembrie 2018 12:08:42
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");

vector <pair<int,int> > a;
stack <int> s;
int lg=0;

int main(){
	
	int n;cin>>n;

	for(int i=1;i<=n;i++){
		int nr;cin>>nr;

		int mx=0;
		for(int j=0;j<a.size();j++)
			if(a[j].first<nr and a[j].second>mx)
				mx=a[j].second;
		
		lg=max(mx+1,lg);
		a.push_back(make_pair(nr,mx+1));
	}
	
	int pozmx=n-1,val=2000000001;
	
	cout<<lg<<endl;
	
	for(int i=lg;i>=1;i--){
			
		int poz=n;
		for(int j=0;j<=pozmx and poz==n;j++)
			if(a[j].second==i and val>a[j].first)poz=j;
			
		pozmx=poz;
		val=a[poz].first;
		s.push(a[poz].first);
	}
		
	while(!s.empty()){
		cout<<s.top()<<" ";
		s.pop();}		

	return 0;
}