Cod sursa(job #1455299)

Utilizator petru.cehanCehan Petru petru.cehan Data 27 iunie 2015 15:09:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("scmax.in") ;
ofstream fout ("scmax.out") ;

long int v[100001], l[100001] , n , i , k , maxim , t;

void Citire()
{
    fin >> n;
    for ( i = 1 ; i <= n ; ++i )
         fin >> v[i] ;
}

void SubsirCrescatorMaximal ( long int n , long int v[] )
{
    l [n] = 1 ;
    for ( k = n-1 ; k >=1 ; -- k )
       {
           maxim = 0;
           for ( i = k + 1 ; i <= n ; ++ i )
            if ( v[i] > v[k] && l[i] > maxim )
                    maxim = l[i];
        l[k] = 1 + maxim;
       }

    maxim = l[1];
    t = 1;

    for ( i = 2 ; i <= n ; ++ i )
       if ( l[i] > maxim )
           {
               maxim = l[i];
               t = i;
           }
    fout << maxim << "\n" ;
    fout<<v[t]<<" ";
    for ( i = t + 1 ; i <= n ; ++ i )
      if ( v[i] > v[t] && l[i] == maxim - 1 )
           --maxim , fout << v [i] << " ";
}

int main()
{
    Citire ();
    SubsirCrescatorMaximal ( n , v );
    return 0;
}