Cod sursa(job #3354896)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 21 mai 2026 09:28:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
vector<int>parent;
vector<int>v;
vector<int>rez;
void rec(int &poz){
    if(poz==-1){
        return;
    }
    rez.push_back(v[poz]);
    rec(parent[poz]);
}
int main(){
    int n;
    fin>>n;
    v.resize(n);
    for(int i=0;i<n;++i){
        fin>>v[i];
    }
    vector<int>lung(n);
    parent.resize(n);
    parent[0]=-1;
    for(int i=0;i<n;++i){
        lung[i]=1;
        for(int j=0;j<i;++j){
            if(v[j]<v[i]){
                if(lung[j]+1>lung[i]){
                    lung[i]=lung[j]+1;
                    parent[i]=j;
                }
            }
        }
        if(lung[i]==1){
            parent[i]=-1;
        }

    }
    int final=0;
    int maxi=0;
    for(int i=0;i<n;++i){
        if(lung[i]>maxi){
            final=i;
            maxi=lung[i];
        }
    }
    fout<<maxi<<"\n";
    rec(final);
    for(int i=rez.size()-1;i>=0;--i){

        fout<<rez[i]<<" ";
    }
    return 0;
}