Cod sursa(job #648517)

Utilizator dany123Florea Daniel dany123 Data 13 decembrie 2011 17:05:54
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<iostream>
#include<fstream>
using namespace std;
int n, v[100001],dp[100001],pre[100001],sir[100001];
int maxx,imax;
void citire()
{
	ifstream fin ("scmax.in");
	fin>>n;
	for (int i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
}
void scr()
{
	//pre[1]=0;
	dp[1]=1;
	for (int i=2;i<=n;i++)
	{
		dp[i]=1;
		//pre[i]=0;
		for (int j=i-1;j>=1;j--)
			if (v[i]>v[j])
			{
				dp[i]=dp[j]+1;
				pre[i]=j;
				if (dp[i]>maxx) {maxx=dp[i]; imax=i;}
				break;
			}
	}
}
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();
	/*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]<<' ';*/
	reconst();
}