Cod sursa(job #1124709)

Utilizator GoldEagleAndrei Iulian GoldEagle Data 26 februarie 2014 13:22:41
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
/*
 * Created on: 26th February 2014
 * Author: <Marin Iulian Andrei>
 * Description: determinarea unui subsir crescator maximal;
 * Abordarea dinamica a problemei - neoptim complet;
 */

 #include <fstream>
 #define NMAX 100001
 using namespace std;

 long long v[NMAX],d[NMAX],p[NMAX];
 long n,k;
 //p[i] - lungimea maxima a unui subsir;
 //d[i] - pozitia urmatorului element pentru recontruirea subsirului maximal

 fstream g ("scmax.out",ios::out);

 void read_data ()
 {
     fstream f ("scmax");
     f>>n;
     for (int i=1;i<=n;++i)
        f>>v[i];
     f.close();
 }

 void print (int q)
 {
     while (q)
     {
         g<<v[p[q]]<<" ";
     }
     g.close();
 }

 void solve ()
 {
     int i,j,max,max2=n,poz;

     d[n]=1;
     p[n]=0;
     for (i=n-1;i>=1;i--)
     {
         poz=0;
         max=0;
         for (j=i+1;j<=n;++j)
            if ((v[i] > v[j]) && (d[j] > max) )
         {
             max=d[j];
             poz=j;
         }
         d[i]=max+1;
         poz=j;
        if (d[i] > d[max2]) max2=i;

     }
    g<<d[max2]<<'\n';
    print (max2);
 }

 int main (void)
 {
     read_data();
     solve();

     return 0;
 }