Cod sursa(job #1448920)

Utilizator tudoras8tudoras8 tudoras8 Data 8 iunie 2015 12:46:21
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>

using namespace std;

int N, *A, *L, maxx, Lmax;

void dinamica() {
    L = new int[N + 1];

    L[N] = 1;
    for (int i = N - 1; i >= 1; --i) {
        maxx = 0;
        for (int j = i + 1; j <= N; ++j) {
            if (L[j] > maxx && A[i] <= A[j]) {
                maxx = L[j];
            }
        }
        L[i] = maxx + 1;

        if (Lmax < L[i]) {
            Lmax = L[i];
        }
    }
}

void drum() {
    cout << Lmax << "\n";
    int Lseq = Lmax, t = 1, p = 1;
    do {
        while (!(Lseq == L[p] && A[t] <= A[p])) {
            p++;
        }
        cout << A[p] << " ";
        t = p;

        --Lseq;
    } while (Lseq > 0);
}

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    cin >> N;
    A = new int[N + 1];
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    dinamica();
    drum();

    delete [] A;
    delete [] L;

    return 0;
}