Cod sursa(job #694049)

Utilizator TheOnlyExceptionBarna Monica TheOnlyException Data 27 februarie 2012 18:20:40
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,v[100003],i,loc[100003],j,nr;

void citire()
{
	f >> n;
	for(i=1;i<=n;i++)
		f >> v[i];
}

int search(int x)
{
	for(j=n;j>=x;j--)
		if(v[x]<v[j])
			return loc[j]+1;
	return 1;
}
		

void locul()
{
	loc[n]=1;
	for(i=n-1;i>=1;i--)
	{
		if(v[i]<v[i+1])
			loc[i]=loc[i+1]+1;
		else
			loc[i]=search(i);
		if(loc[i]>nr) nr=loc[i];
	}
	g << nr << "\n";
}

void subsir()
{
	for(i=1;i<=n;i++)
	{
		if(loc[i]==nr)
		{
			g << v[i] << " ";
			nr=nr-1;
		}
		if(nr==0) break;
	}
}

int main()
{
	citire();
	locul();
	subsir();
	return 0;
}