Cod sursa(job #1308976)

Utilizator addyyyBardan Adrian addyyy Data 4 ianuarie 2015 23:30:53
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
using namespace std;
ifstream f("nr.in");
ofstream g("nr.out");
int vi[100001],vf[100001],l[100001];
int main()
{
	int n,i,j,max1=0,poz,nr,k=0;
	f>>n;
	for(i=0;i<n;i++)
		f>>vi[i];
	l[0]=1;
	poz=0;
	for(i=1;i<n;i++)
	{
		if(max1<l[i-1])
		{
			max1=l[i-1];
			poz=i-1;
		}
		if(vi[poz]<vi[i])
			l[i]=l[poz]+1;
		else
		{
			j=i-1;
			while(vi[i]<=vi[j])
				j--;
			l[i]=l[j]+1;
		}
	}
	if(max1<l[n-1])
		max1=l[n-1];
	g<<max1<<"\n";
	nr=max1;
	i=n-1;
	while(nr>=1&&i>=0)
	{
		if(nr==l[i])
		{
			vf[k++]=vi[i];
			nr--;
		}
		i--;
	}
	for(i=k-1;i>=0;i--)
		g<<vf[i]<<" ";
}