Cod sursa(job #648534)

Utilizator dany123Florea Daniel dany123 Data 13 decembrie 2011 17:37:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
//subsir crescator maximal 13.12.2011
#include<iostream>
#include<fstream>
using namespace std;
int n, v[100001],dp[100001],pre[100001],sir[100001];
int maxx=-1,imax;
void citire()
{
	ifstream fin ("scmax.in");
	fin>>n;
	for (int i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
}
void scr()
{
	dp[1]=1;
	for (int i=2;i<=n;i++) 
	{
		dp[i]=1;
		for (int j=i-1;j>=1;j--) 
			if (v[i]>v[j] && dp[i]<dp[j]+1) //daca e mai mare si daca dist+1 pana la j > dist pana la i
			{
				dp[i]=dp[j]+1;
				pre[i]=j;
				if (dp[i]>maxx) {maxx=dp[i]; imax=i;}
			}
	}
}
void reconst()
{
	ofstream fout("scmax.out");
	fout<<maxx<<'\n';
	
	int i=imax;
	int j=1;
	while (i>0)
	{
		sir[j++]=v[i];
		i=pre[i];
	}
	
	for (int i=maxx;i>=1;i--)
		fout<<sir[i]<<' ';
	fout.close();
}
int main ()
{
	citire();
	scr();
	/*
	int d=0;
	if (d)
	{
		cout<<"\ni: ";
		for (int i=1;i<=n;i++) cout<<v[i]<<' ';
		cout<<"\ndp: ";
		for (int i=1;i<=n;i++) cout<<dp[i]<<' ';
		cout<<"\npre: ";
		for (int i=1;i<=n;i++) cout<<pre[i]<<' ';
		cout<<'\n';
	}
	*/
	reconst();
	return 0;
}