Cod sursa(job #2902103)

Utilizator Frant_IoanaFrant Ioana Frant_Ioana Data 15 mai 2022 16:41:02
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 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] << ' ';
}