Cod sursa(job #568182)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 30 martie 2011 21:42:00
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>

using namespace std;

long X[100005], N, L[100005], LMax, imax, Subsir[100005];

void citire ()
{
	ifstream fin ("scmax.in");
	int i;
	fin >> N;
	for (i=1; i<=N; i++)
	{
		fin >> X[i];
	}
	fin.close ();
}

void afisare ()
{
	ofstream fout ("scmax.out");
	long i, l;
	l=LMax;
	fout << l << "\n";
	Subsir[l]=X[imax];
	for (i=imax-1; i>=0; i--)
	{
		if (L[i]==l-1)
		{
			l--;
			Subsir[l]=X[i];
		}
		if (l==0)
		{
			break;
		}
	}
	for (i=1; i<=LMax; i++)
	{
		fout << Subsir[i] << " ";
	}
	fout << "\n";
	fout.close ();
}

int main()
{
	int i, j;
	citire ();
	L[1]=1;
	for (i=2; i<=N; i++)
	{
		j=i-1;
		while (X[j]>=X[i])
		{
			j--;
		}
		L[i]=1+L[j];
		if (L[i]>LMax)
		{
			LMax=L[i];
			imax=i;
		}
	}
	afisare ();
	return 0;
}