Cod sursa(job #867238)

Utilizator PlatonPlaton Vlad Platon Data 29 ianuarie 2013 13:36:47
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>

using namespace std;

int a[100001], l[100001],poz, k,i,mx,maxa,n;

int main()
{
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	
	f>>n;
	for(i=1;i<=n;i++)
	{
		f>>a[i];
	}
	
	l[n]=1;
	for(i=n-1;i>=1;i--)
	{
		for(k=i+1;k<=n;k++)
		{
			if(a[i]<a[k])
			{
				l[i]=l[k]+1;
				if(l[k]+1>maxa)
				{
					maxa=l[k]+1;
					poz=i;
				}
				break;
			}
		}
		if(l[i]==0)
		{
			l[i]=1;
		}
	}
	g<<maxa<<"\n";
	g<<a[poz]<<" ";
	for(i=1;i<=n;i++)
	{
		if(l[i]==maxa-1)
		{
			g<<a[i]<<" ";
			maxa--;
		}
	}
	
	return 0;
}