Cod sursa(job #1706512)

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

using namespace std;

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

int a[100001], d[100001], p[100001], n, k;

void dinamica (){
	int max, max2=n, poz;
	d[n]=1;
	p[n]=0;
	for (int i=n-1; i>=1; i--){
		poz=0; max=0;
		for (int j=i+1; j<=n; j++)
			if (a[i]<a[j] && d[j]>max){
				max=d[j];
				poz=j;
			}
		d[i]=1+max;
		p[i]=poz;
		if (d[i]>d[max2]) max2=i;
	}
	cout<<d[max2]<<'\n';
	while (max2>0){
		cout<<a[max2]<<" ";
		max2=p[max2];
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dinamica();
	return 0;
}