Cod sursa(job #1653877)

Utilizator octavian.sndOctavian Sandu octavian.snd Data 16 martie 2016 17:48:01
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long v[100], subsir[100], n;

long celMaiLungSubsirOrdonat(int v[] , int n , int subsir[]){
    int lungime, inceput, i, j;
    int *maxime = new int[n];
    int *urmatorul = new int[n];

    maxime[n - 1] = 1;
    urmatorul[n - 1] = -1;
    for(i = n - 2; i >= 0; i--){
        maxime[i] = 1;
        urmatorul[i] = -1;
        for(j = i + 1; j < n; j++)
            if(v[i] < v[j] && maxime[i] <= maxime[j]){
                maxime[i] = maxime[j] + 1;
                urmatorul[i] = j;
            }
    }
    lungime = maxime[0];
    inceput = 0;
    for(i = 1; i < n; i++)
        if(lungime < maxime[i]){
            lungime = maxime[i];
            inceput = i;
        }
    subsir[0] = v[inceput];
    for(i = 1; i < lungime; i++){
        inceput = urmatorul[inceput];
        subsir[i] = v[inceput];
    }
    delete urmatorul;
    delete maxime;
    return lungime;
}

int main(){
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
    int l = celMaiLungSubsirOrdonat(v , n , subsir);
    fout << l << '\n';
    for(int i = 1; i <= l; ++i)
        fout << subsir[i] << " ";
    return 0;
}