Cod sursa(job #2777010)

Utilizator Florian11232Florian Susai Florian11232 Data 21 septembrie 2021 19:55:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;

#define dim 100001

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

int v[dim], bst[dim], back[dim];

void scmax(int pos) {
    if (back[pos] == -1) {
        out << v[pos] << " ";
        return;
    }

    scmax(back[pos]);
    out << v[pos] << " ";
}

int main()
{
    int n, i, lmax,pos_f;
    
    in >> n;
    for(i = 1; i <= n; i++) {
        in >> v[i];
    }
    
    bst[1] = 1;
    back[1] = -1;
    lmax = 1;
    pos_f = 1;
    for(i = 2; i <= n; i++) {
        bst[i] = 1;
        back[i] = -1;
        for(int j = 1; j < i; j++)
        {
            if(bst[i] < bst[j]+1 && v[j]<v[i]) {
                bst[i] = bst[j] + 1;
                back[i] = j;
                if (bst[i] > lmax) {
                    lmax = bst[i];
                    pos_f = i;
                }
            }
        }
    }


    // int pos = pos_f;
    // while(back[pos] != -1) {
    //     out << v[pos] << " ";
    //     pos = back[pos];
    // }  

    // out << v[pos] << "\n";

    out << lmax << '\n'; 

    scmax(pos_f);

    return 0;
}