Cod sursa(job #508444)

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

int main()
{
	int 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];
		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);
	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]);
}