Cod sursa(job #2648605)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 11 septembrie 2020 18:10:43
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <cmath>

#define MOD 666013

using namespace std ;

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

int v[100009], l[100009], poz_prev[100009] ;

void recur(int f)
{
    if(!f)return ;

    recur(poz_prev[f]) ;

    cout << v[f] << " " ;

}

int main()
{
    int n ;

    cin >> n ;

    for(int f = 1, x ; f <= n ; f ++)
        cin >> v[f] ;

    for(int f = 1 ; f <= n ; f ++)
    {

        for(int e = 1 ; e <= f ; e ++) /// sunt eligibile numai elementele care sunt mai mici ca v[f]
            if(v[e] < v[f] && l[e] + 1 > l[f])
            {

                l[f] = l[e] + 1 ;

                poz_prev[f] = e ;
            }

        if(!poz_prev[f])l[f] = 1 ;

    }

    int mx = 0, mxf = 0 ;

    for(int f = 1 ; f <= n ; f ++)
        mx = max(l[f], mx) ;

    for(int f = 1 ; f <= n ; f ++)
        if(l[f] == mx)
        {

            mxf = f ;

            break ;

        }

    cout << mx << endl ;

    recur(mxf) ;

    return 0 ;
}