Cod sursa(job #2066676)

Utilizator benjamin2205Zeic Beniamin benjamin2205 Data 15 noiembrie 2017 11:56:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("scmax.in");
ofstream g ("scmax.out");

int n;
int maxGlobal;
int indiceFinal;

int sirInit[100005];
int lungime[100005];
int memorie[100005];

stack <int> stiva;

void afisareSir(int*, int);
void citire();

void afisareSolutie() {
    g << maxGlobal << '\n';
    while(indiceFinal != 0) {
        stiva.push(sirInit[indiceFinal]);
        indiceFinal = memorie[indiceFinal];
    }
    while(!stiva.empty()) {
        g << stiva.top() << ' ';
        stiva.pop();
    }

    g << '\n';
}

void rezolvare() {
    int maxim;
    for (int i = 1; i <= n; ++i) {
        maxim = 0;
        lungime[i] = 1;
        for (int j = i - 1; j >= 1; --j) {
            if (sirInit[i] > sirInit[j] &&
                maxim < lungime[j]) {
                lungime[i] = 1 + lungime[j];
                maxim = lungime[j];
                memorie[i] = j;
                if (maxGlobal < lungime[i]) {
                    maxGlobal = lungime[i];
                    indiceFinal = i;
                }
            }
        }
    }
//    afisareSir(lungime, n);
//    afisareSir(memorie, n);
    afisareSolutie();
}

void maxim() {
    int maxim = 0;
    for (int i = 1; i <= n; ++i) {
        maxim = max(lungime[i], maxim);
    }
    g << maxim;
}

int main()
{
    citire();
    rezolvare();
    //afisareSir(lungime, n);
    //maxim();

    return 0;
}

void citire() {
    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> sirInit[i];
    }
}

void afisareSir(int a[], int n) {
    for (int i = 1; i <= n; ++i) {
        g << a[i] << ' ';
    }
    g << '\n';
}