Cod sursa(job #609214)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 20 august 2011 10:18:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <cstdio>
#include <iostream>
using namespace std;

int v[100013],dp[100013],urm[100013],poz;

int main()
{	
	int i,n,j;
	freopen("scmax.in","r", stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++) 
		scanf("%d",&v[i]);
	for(i=n;i>=1;i--)
	{
		dp[i]=1;
		for(j=i+1;j<=n;j++)
		{
			if(v[i]<v[j] && dp[i]<dp[j]+1) 
			{
				dp[i]=dp[j]+1;
				urm[i]=j;
			}
		}
		if(dp[i]>dp[poz]) poz=i;	
	}
	freopen("scmax.out","w", stdout);
	cout<<dp[poz]<<"\n";
	for(i=poz;i!=0;i=urm[i])
	{
		cout<<v[i]<<" ";
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}