Cod sursa(job #1115935)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 22 februarie 2014 10:47:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
using namespace std;
int main ()
{
    ifstream  f("scmax.in");
    ofstream g("scmax.out");
    int v[100000],i,n,l[100000],j,max,tati[100000],maxim=-1,pozmax,x,cont=0;
    f>>n;
    for (i=1; i<=n; i++)
    f>>v[i];


    l[n]=1; tati[n]=0;
    for (i=n-1; i>=1; i--)
    {
       max=-1;
    for (j=i+1; j<=n; j++)
    if (l[j]>max && v[i]<v[j] )
    { max=l[j];
        tati[i]=j;
    }


    l[i]=max+1;
    }

    for (i=1; i<=n; i++)
    if (l[i]>maxim)
    {
        maxim=l[i];
        pozmax=i;
    }

x=pozmax;
    do
    {

        x=tati[x];
        cont++;
    }
    while ( x!= 0) ;
    g<<cont<<'\n';
    x=pozmax;
    do
    {
        g<<v[x]<<" ";
        x=tati[x];

    }
    while ( x!= 0) ;


   // for (i=1; i<=n; i++)
   // g<<l[i]<<" ";
   // g<<'\n';
   // for (i=1; i<=n; i++)
   // g<<tati[i]<<" ";
    return 0;

}