Cod sursa(job #508438)

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

int main()
{
	long n,i,j,a[100001],b[100001][2],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];
		if (a[i]>=a[i-1])
		{
			if (a[i]==a[i-1])
				{b[i][0]=b[i-1][0];b[i][1]=b[i-1][1];}
			else
				{b[i][0]=b[i-1][0]+1;b[i][1]=i-1;}
		}
		else
		{
			for (j=i-2;j>-1;--j)
			{
				if (a[i]>a[j])
				{
					b[i][0]=b[j][0]+1;
					b[i][1]=j;
					break;
				}
			}
			if (j==-1)
			{
				b[i][0]=1;
				b[i][1]=-1;
			}
		}
	}
	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);
	while (b[k][1]!=-1)
	{
		printf("%d ",a[k]);
		k=b[k][1];
	}
	printf("%d ",a[k]);
}