Cod sursa(job #508468)

Utilizator eudummyEduard eudummy Data 8 decembrie 2010 14:14:33
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 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,maxx1,k;
	
	ifstream f ("scmax.in");
	freopen("scmax.out", "w", stdout);
	f>>n;
	f>>a[0];
	b[0][0]=1;
	b[0][1]=-1;
	maxx1=0;
	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;
		if (maxx1<b[i][0])
		{
			maxx1=b[i][0];	
			k=i;
		}
	}
	printf("%d \n", maxx1);
	n=maxx1;
	while (b[k][1]!=-1)
	{
		c[maxx1-1]=a[k];
		maxx1--;
		k=b[k][1];
	}
	c[0]=a[k];
	for (i=0;i<n;i++)
	printf("%d ",c[i]);
}