Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok

Cod sursa(job #1325756)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 24 ianuarie 2015 12:33:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int v[100010];
int n;
int i, j;
int L[100010];
int maxim, M;
int t[100010];
int p, u;
int sol[100010];
int k;

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

    L[1] = 1;
    t[1] = 0;
    M = 1;
    for (i=2; i<=n; ++i) {
        maxim = 0;
        for (j=1; j<i; ++j)
            if ((L[j] > maxim) && (v[j] < v[i])) {
                maxim = L[j];
                p = j;
            }
        L[i] = 1 + maxim;
        if (maxim == 0)
            t[i] = 0;
        else
            t[i] = p;

        if (L[i] > M) {
            M = L[i];
            u = i;
        }
    }

    fout << M << "\n";
    while (u != 0) {
        sol[++k] = v[u];
        u = t[u];
    }

    for (i=M;i>=1;i--)
        fout<<sol[i]<<" ";

    return 0;
}