Cod sursa(job #2902055)

Utilizator Frant_IoanaFrant Ioana Frant_Ioana Data 15 mai 2022 11:33:35
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, v[100001], lung[100001], i, j, lmax = -1, rez[100001], k;

int main(){
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> v[i];

    lung[1] = 1;

    for(i = 2; i <= n; i++){
        int maxi = 0;

        for(j = 1; j < i; j++)
            if(v[j] < v[i] && lung[j] > maxi)
                maxi = lung[j];
        
        lung[i] = maxi + 1;

        if(lung[i] > lmax)
            lmax = lung[i];
    }

    fout << lmax << '\n';

    int l = lmax, i = n;
    while(lmax){
        if(lung[i] == lmax)
            rez[++k] = v[i], lmax--;
        i--;
    }

    for(i = k; i >= 1; i--)
        fout << rez[i] << ' ';
}