Cod sursa(job #2129815)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 13 februarie 2018 09:48:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

unsigned int N, LMax, poz, L[100003], a[100003], sol[100003];

int main() {
    f >> N;
    L[1] = 1;
    f >> a[1];
    for(int i = 2; i <= N; i++) {
        f >> a[i];
        int Max = 0;
        for(int j = i - 1; j >= 1; j--)
            if(Max < L[j] && a[j] < a[i])
                Max = L[j];
        L[i] = Max + 1;
        if(LMax < Max + 1) LMax = Max + 1, poz = i;
    }
    int nr = 0;
    sol[++nr] = a[poz];
    LMax--;
    for(int i = poz - 1; i >= 1; i--) {
        if(L[i] == LMax && a[i] < sol[nr]) {
            sol[++nr] = a[i];
            LMax--;
        }
    }
    g << nr << "\n";
    for(int i = nr; i >= 1; i--)
        g << sol[i] << " ";
    g << "\n";
    return 0;
}