Cod sursa(job #2571668)

Utilizator YetoAdrian Tonica Yeto Data 5 martie 2020 09:22:52
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;
int n, i, j, k, maxim=-1, poz;
int v[100001], l[100001], sol[100001];
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

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

    for (i=1;i<=n;i++) {
        l[i]=1;
        for (j=i-1;j>=1;j--) {
            if (v[i]>v[j]) {
                if (l[i]<l[j]+1) {
                    l[i]=l[j]+1;
                }
                if (l[i]>maxim) {
                    maxim=l[i];
                    poz=i;
                }
            }
        }
    }
    fout<<maxim<<"\n";
    k=maxim;
    sol[k--]=v[poz];
    for (i=poz-1;i>=1 && k>0;i--) {
        if (v[i]<sol[k+1] && l[i]==k) {
            sol[k--]=v[i];
        }
    }
    for (i=1;i<=maxim;i++) {
        fout<<sol[i]<<" ";
    }
    return 0;
}