Cod sursa(job #2092203)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 21 decembrie 2017 12:18:21
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#define NN 100001
using namespace std;

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

int v[100001] , n ,next[NN],best[NN];
 void read()
 {
     in >> n ;
     for ( int i =1 ; i <= n ; ++i )
             in>> v[i];
 }

int main()
{  read();
            next[n] = -1 ;
              best[n] = 1 ;
                 for ( int i = n-1 ; i ; --i )
                 {
                        next[i] = -1 , best[i] = 1 ;
                           for ( int j = i ; j <= n ;++ j )
                           {
                               if (v[j]>v[i] && best[j] >= best[i])
                                   best[i]=best[j] +1 , next [i] = j ;
                           }
                 }
                  int poz =  -1 ;
                  int maxim = -1 ;

       for ( int i =1 ; i <= n ;++ i )
                if (best[i] > maxim )
                {
                    maxim = best[i];
                    poz = i ;
                }

        out << maxim <<"\n";
        out << v[poz]<< " ";

        while(next[poz]!=-1)
        {
            poz = next[poz];
            out << v[poz];
            out <<" ";
        }






    return 0;
}