Cod sursa(job #264760)

Utilizator rayvianPricope Razvan rayvian Data 22 februarie 2009 18:26:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iostream>
using namespace std;

int  n;
int  v[100000];
int  par[100000];
int  lung[100000];

void citire();
void rezolva();

int main()
{
	citire();
	rezolva();


	return 0;
}

void rezolva()
{
	int parinte=0;
	int lmax=0;

  int Lungime_Maxima=0;
  int Poz_Lungime_Maxima=0;
	for(int i=n; i>=1; i--)
	{
		lmax=0;
    parinte=0;

		for(int j=i+1; j<=n; j++)
		{
			if(v[i]<v[j] &&	lung[j]>lmax)
			{
      	parinte=j;
				lmax=lung[j];
			}
		}
    lmax++;
		lung[i]=lmax;
    par[i]=parinte;
    if(lmax>Lungime_Maxima)
    {
    	Lungime_Maxima=lmax;
      Poz_Lungime_Maxima=i;
    }

	}

  int var=Poz_Lungime_Maxima;

  fstream f;
  f.open("scmax.out",ios::out);
  f<<Lungime_Maxima<<endl;
  while(var)
  {
  	f<<v[var]<<" ";
    var=par[var];
  }

  f.close();
}


void citire()
{
	fstream f;
	f.open("scmax.in",ios::in);
	f>>n;
	for(int i=1; i<=n; i++)
		f>>v[i];
	f.close();
}