Cod sursa(job #239765)

Utilizator mihai.cuculiciCuculici Mihail mihai.cuculici Data 5 ianuarie 2009 19:34:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");

int DP(long v[], long n, long subsir[])
{
  long lungime,inceput,i,j;
  long *maxime=new long[n];
  long *urmatorul=new long[n];
  maxime[n-1]    = 1;
  urmatorul[n-1] =-1;
  for(i=n-2;i>=0;i--)
  {
      maxime[i]    = 1;
      //urmatorul[i] =-1;
      for(j=n-1;j>i;j--)
         if((v[i]<v[j])&&(maxime[i]<=maxime[j])) maxime[i]=maxime[j]+1,urmatorul[i]=j;
  }
  lungime = maxime[0];
  inceput = 0;
  for(i=1;i<n;i++)
      if(lungime<maxime[i]) lungime=maxime[i],inceput=i;
  subsir[0] = v[inceput];
  for(i=1;i<lungime;i++) inceput=urmatorul[inceput],subsir[i]=v[inceput];
  return lungime;
}

int main()
{
    long n,x;
    f>>n;
    long *v=new long[n];
    long *s=new long[n];
    for(int i=0;i<n;i++) f>>v[i];
    x=DP(v,n,s);
    g<<x<<"\n";
    for(int i=0;i<x;i++) g<<s[i]<<" ";
    f.close();
    g.close();
    return 0;
}