Cod sursa(job #802453)

Utilizator shuleavSulea Vlad shuleav Data 26 octombrie 2012 18:50:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100010],n,i,L[100010],j,maxi,maxL,poz[100010],M,ANS[100000],t;
int main()
{
	f >> n;
	for(i=1;i<=n;i++)
		f >> a[i];
	L[1]=1;
	for(i=2;i<=n;i++)
	{
		maxi=0;
		for(j=i-1;j>=1;j--)
			if(a[j]<a[i] && maxi<L[j])
			{
				maxi=L[j];
				poz[i]=j;
			}
		L[i]=maxi+1;
	}

	maxL=0;
	for(i=1;i<=n;i++)
		if(maxL<L[i])
		{
			maxL=L[i];
			M=i;
		}
	t=1;
	while (M!=0)
	{
		ANS[t]=a[M];
		M=poz[M];
		t++;
	}

	g << maxL << '\n';

	for(i=t-1;i>=1;i--)
		g << ANS[i] << ' ';
	g << '\n';

	f.close();
	g.close();
    return 0;
}