Cod sursa(job #238084)

Utilizator mihai.cuculiciCuculici Mihail mihai.cuculici Data 31 decembrie 2008 14:58:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");

int DP(long long v[], long long n, long long subsir[])
{
  long long lungime,inceput,i,j;
  long long *maxime    = new long long[n];
  long long *urmatorul = new long 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=i+1;j<n;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 long v[100000],n,s[100000],x;
    f>>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;
}