Cod sursa(job #1608146)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 21 februarie 2016 21:09:36
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
# include <fstream>
# define    MAXN    100010
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, i, j, maxx, maxk;
int v[MAXN], D[MAXN], t[MAXN];

void parinte(int idx) {
    if (!idx)
        return;

    fout << v[idx] << " ";
    parinte(t[idx]);
}

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

    D[n] = 1;
    t[n] = 0;
    for (i=n-1; i>0; --i) {
        D[i] = 1;
        t[i] = i;
        for (j=i+1; j<=n; ++j)
            if (D[j] >= D[i] && v[i] < v[j]) {
                D[i] = 1 + D[j];
                t[i] = j;
            }
    }

    for (i=1; i<=n; ++i)
        if (maxx < D[i])
            maxx = D[i],
            maxk = i;

    fout << maxx << "\n";
    parinte(maxk);

    return 0;
}