Cod sursa(job #719931)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 22 martie 2012 10:42:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int main()
{
	int a[100005],l[100005],next[100005],n;
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>a[i];
	l[n]=1;
	next[n]=-1;
	for(int i=n-1;i>=1;i--)
	{
		l[i]=1;
		next[i]=-1;
		for(int j=i+1;j<=n;j++)
			if(a[i]<a[j] && l[i]<1+l[j])
			{
				l[i]=1+l[j];
				next[i]=j;
			}
	}
	int pmax=0;
	l[0]=-1;
	for(int i=1;i<=n;i++)
		if(l[i]>l[pmax])
			pmax = i;
	fout<<l[pmax]<<'\n';
	for( ; pmax!=-1;pmax=next[pmax])
		fout<<a[pmax]<<' ';
	
	
	return 0;
}