Cod sursa(job #1469312)

Utilizator mihaiadelinamihai adelina mihaiadelina Data 8 august 2015 00:19:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
/*
v:         24 12 15 15 25
maxime:     2  3  2  2  1
urmatorul:  4  2  4  4 -1
*/
int n, v[100001], urmatorul[100001], maxime[100001];
// maxime[i] = lungimea celui mai mare subsir crescator care incepe la pozitia i
// urmatorul[i] = pozitia celui de-al doilea element al subsirului folosit pt calcularea lui maxime[i]

void celMaiLungSubsirOrdonat() {
    int i, j, lungime, inceput;

    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;
        }
    }

    fout << lungime << "\n";
    int poz = inceput;
    for (i = 0; i < lungime; i++) {
        fout << v[poz] << " ";
        poz = urmatorul[poz];
    }
}

int main() {
    int i;

    fin >> n;

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

    celMaiLungSubsirOrdonat();

    return 0;
}