Cod sursa(job #508463)

Utilizator eudummyEduard eudummy Data 8 decembrie 2010 14:06:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

int main()
{
	long n,i,j,a[100001],b[100001][2],c[100001],maxx,k;
	
	ifstream f ("scmax.in");
	freopen("scmax.out", "w", stdout);
	f>>n;
	f>>a[0];b[0][0]=1;b[0][1]=-1;
	for (i=1;i<n;i++)
	{
		f>>a[i];
		maxx=0;k=-1;
		for (j=0;j<i;j++)
			if ((maxx<b[j][0])&&(a[i]>a[j]))
			{
				maxx=b[j][0];	
				k=j;
			}
		b[i][0]=maxx+1;
		b[i][1]=k;
	}
	maxx=1;
	k=0;
	for (i=0;i<n;i++)
		if (maxx<b[i][0])
		{
			maxx=b[i][0];	
			k=i;
		}
	printf("%d \n", maxx);
	n=maxx;
	while (b[k][1]!=-1)
	{
		c[maxx-1]=a[k];
		maxx--;
		k=b[k][1];
	}
	c[0]=a[k];
	for (i=0;i<n;i++)
	printf("%d ",c[i]);
}