Cod sursa(job #2921651)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 1 septembrie 2022 11:54:09
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;

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

int n;
int v[100005];
int lung[100005];
int lmax,pmax;
int last_el;
int t[100005];
int dim;

void citire() {
    f >> n;
    for (int i=1;i<=n;i++) {
        f >> v[i];
    }
}

int main()
{
    citire();
    for (int i=1;i<=n;i++) {
        lung[i]=1;
        for (int j=1;j<i;j++) {
            if (v[j]<v[i]) {
                lung[i] = max(lung[i],lung[j]+1);
                if (lung[i]>lmax) {
                    lmax = lung[i];
                    last_el = v[i];
                }
            }
        }
    }
    g << lmax << '\n';
    last_el++;
    for (int j=n;j>=1;j--) {
        if (lung[j]==lmax && v[j]<last_el) {
            last_el = v[j];
            t[++dim] = v[j];
            lmax--;
        }
    }
    ///t[1]=19  t[2]=15 t[3]=12
    for (int j=dim;j>=1;j--) {
        g << t[j] << " ";
    }
    return 0;
}