Cod sursa(job #229145)

Utilizator serbanlupulupulescu serban serbanlupu Data 9 decembrie 2008 14:57:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
//determinarea celui mai lung subsir dintr-un vector

#include<iostream>
#include<fstream.h>

ifstream f("scmax.in");
ofstream g("scmax.out");

using namespace std;

void afisare(int i,int tata[100000],int v[100000])
{
	if (i==0)
		return;
	afisare(tata[i],tata,v);
	g<<v[i]<<" ";
}

int main()
{
	int v[100000];
	int dp[100000];
	int n,i,j;
	//citesc
	f>>n;
	for (i=1;i<=n;++i)
		f>>v[i];
	//max
	int max=0;
	int tata[100000];
	//incepe algoritmu`
	for (i=1;i<=n;++i)
	{
		dp[i]=1;
		tata[i]=0;
		for (j=1;j<=i-1;++j)
			if (v[i]>v[j] && dp[i]<dp[j]+1)
			{
				dp[i]=dp[j]+1;
				tata[i]=j;
			}
			
		if (dp[max] < dp[i])
			max=i;
	}
	g<<dp[max];
	g<<endl;
	i=max;
	afisare(i,tata,v);
	return 0;
}