Cod sursa(job #663253)

Utilizator sanzianaioneteIonete Sanziana sanzianaionete Data 18 ianuarie 2012 09:48:04
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
using namespace std;
int n,a[100001],s[100001][2],max,poz,i,j;
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d\n",&n);
	for(int i=1;i<=n;i++) scanf("%d ",&a[i]);
	s[n][0]=1;
	for(i=n-1;i>=1;i--)
	{
		int max1=0,p=i;
		for(j=i+1;j<=n;j++)
			if(s[j][0]>max1&&a[i]<a[j])
			{
				max1=s[j][0];
				p=j;
			}
		s[i][0]=max1+1;s[i][1]=p;
		if(max<s[i][0])
		{
			max=s[i][0];
			poz=i;
		}
	}
	printf("%d\n",max);
	for(i=1;i<max;i++)
	{
		printf("%d ",a[poz]);
		poz=s[poz][1];
	}
	printf("%d\n",a[poz]);
	fclose(stdin);fclose(stdout);
	return 0;
}