Cod sursa(job #2115932)

Utilizator hiimsobaDicianu Ioan-Alexandru hiimsoba Data 27 ianuarie 2018 11:26:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std ;

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

int v[100001], l[100001], n, mx, t ;

int main() {
    cin >> n ;

    for(int i = 1 ; i <= n ; i++)
        cin >> v[i] ;

    l[n] = 1 ;

    for(int k = n - 1 ; k >= 1 ; k--) {
        mx = 0 ;
        for(int i = k + 1 ; i <= n ; i++)
            if(v[i] > v[k] and l[i] > mx)
                mx = l[i] ;
        l[k] = 1 + mx ;
    }

    mx = l[1] ;
    t = 1 ;

    for(int k = 1 ; k <= n ; k++) {
        if(l[k] > mx) {
            mx = l[k] ;
            t = k ;
        }
    }

    cout << mx << '\n' <<  v[t]  << ' ' ;

    for(int i = t + 1 ; i <= n ; i++)
        if(v[i] > v[t] and l[i] == mx - 1) {
            cout << v[i] << ' ' ;
            mx-- ;
        }

    return 0 ;
}