Cod sursa(job #422253)

Utilizator metalkittenGeorgiana Arhip metalkitten Data 22 martie 2010 13:43:31
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream>
#include<iostream>
using namespace std;

long a[100001],b[100001],c[100001],n,i,j,maxx;
ifstream f("scmax.in");
ofstream g("scmax.out");

int maxim(long a,long b)
{
	if (a>b) return a;
	return b;
}

int main()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i];
	for(i=1;i<=n;i++)
		b[i]=1;
	for(i=n-1;i>=1;i--)
		for(j=i+1;j<=n;j++)
		{
			if(a[i]<a[j]&&b[i]<=b[j])
				{
					b[i]=b[j]+1;
					c[i]=j;
					maxx=maxim(b[i],maxx);
				}
		}
	i=0;
	g<<maxx<<endl;
	while(b[i]!=maxx)
	i++;
	while(c[i])
	{
		g<<a[i]<<" ";
		i=c[i];
	}
	i=0;

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