Cod sursa(job #2051019)

Utilizator ZenoTeodor Anitoaei Zeno Data 28 octombrie 2017 14:04:08
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define NMAX 100001

using namespace std;

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

struct sir{
    int val, seqLen, root;
}V[NMAX];

int n, cntr;

void path(int ind) {
    if(V[ind].root != -1){
        path(V[ind].root);
        fout << V[ind].val << ' ';
    }
    else fout << V[ind].val << ' ';
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> V[i].val;
        V[i].root = -1;
        V[i].seqLen = 1;
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(V[i].val > V[j].val && V[j].seqLen + 1 > V[j].seqLen) {
                V[i].seqLen = V[j].seqLen + 1;
                V[i].root = j;
            }
        }
    }
    int ma = 0, ind;
    for(int i = 1; i <= n; i++) {
        if(ma < V[i].seqLen) {
            ma = V[i].seqLen;
            ind = i;
        }
    }
    fout << ma << '\n';
    path(ind);
    return 0;
}