Cod sursa(job #1706524)

Utilizator shaghiCatalina Sagan shaghi Data 22 mai 2016 18:48:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
#define MAX 100001

using namespace std;

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

int a[MAX],l[MAX],poz[MAX];
int n,m,prim;

void citire(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
}

void subsir(){
	for(int i=n;i>=1;i--){ 
		l[i]=1;poz[i]=0;
		for(int j=i+1;j<=n;j++)
			if(a[i]<a[j] && l[i]<1+l[j]){
				l[i]=1+l[j];
				poz[i]=j;
			}
		if(m<l[i]) {m=l[i];prim=i;}
	}
}

void tipar(){
	cout<<m<<'\n';
	for(int i=prim;i>0;i=poz[i])
		cout<<a[i]<<' ';
}
int main(){
	citire();
	subsir();
	tipar();
	return 0;
}