Cod sursa(job #503375)

Utilizator cmiNCosmin Poieana cmiN Data 22 noiembrie 2010 19:07:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
using namespace std;

int main()
{
    long n, v[100001], len[100001], i, k, mlen, gmlen, pos;
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> v[i];
    }
    fin.close();
    len[n] = 1;
    gmlen = 1;
    for (k = n - 1; k > 0; k--) {
        mlen = 0;
        for (i = k + 1; i <= n; i++) {
            if (len[i] > mlen && v[i] > v[k]) {
                mlen = len[i];
            }
        }
        len[k] = 1 + mlen;
        if (len[k] > gmlen) {
            gmlen = len[k];
            pos = k;
        }
    }
    fout << gmlen-- << "\n";
    fout << v[pos] << " ";
    for (i = pos + 1; i <= n; i++) {
        if (v[i] > v[pos] && len[i] == gmlen) {
            fout << v[i] << " ";
            gmlen--;
        }
    }
    fout.close();
    return 0;
}