Cod sursa(job #628516)

Utilizator iulynaCretu Irina iulyna Data 1 noiembrie 2011 16:58:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<iostream>
#include<fstream>
using namespace std;
int n,x[100000],z[100000];
int a[100000],q;
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	cin>>n;
	int p,mxm=0,i,j,mx=0;
	for(i=1;i<=n;i++)
	{
		mx=0;
		cin>>x[i];
		for(j=1;j<i;j++)
			if(x[j]<x[i]&&mx<z[j])
				mx=z[j];
		z[i]=mx+1;
		if(mx+1>mxm)
			mxm=mx+1,p=i;
	}
	cout<<mxm<<'\n';
	a[++q]=x[p];
	for(i=p-1;i>=1;i--)
		if(z[i]==mxm-1&&x[i]<x[p])
			p=i,a[++q]=x[i],mxm--;
	
	for(i=q;i>=1;i--)
		cout<<a[i]<<" ";
	
	return 0;
}