Cod sursa(job #1001275)

Utilizator RusuRusu Daniel Rusu Data 24 septembrie 2013 19:54:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

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

struct element {
    int e, mx, nxt;
};

element v[100001];
int n, i, j, mx;

int main() {
    fin >> n;

    for(i = 1;i <= n;i++) {
        fin >> v[i].e;
    }
    mx = n;
    v[n].mx = 1;
    v[n].nxt = 0;
    for(i = n - 1;i > 0;i--) {
        v[i].nxt = 0;
        v[i].mx = 1;
        for(j = i + 1;j <= n;j++) {
            if(v[j].e > v[i].e && v[j].mx >= v[i].mx) {
                v[i].mx = v[j].mx + 1;
                v[i].nxt = j;
            }
        }
        if(v[mx].mx < v[i].mx) mx = i;
    }

    fout << v[mx].mx << '\n';

    while(mx != 0) {
        fout << v[mx].e << ' ';
        mx = v[mx].nxt;
    }

    fin.close();
    fout.close();

    return 0;
}