Pagini recente » Cod sursa (job #2188793) | Cod sursa (job #411062) | Cod sursa (job #3248349) | Cod sursa (job #1398486) | Cod sursa (job #1469312)
#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;
}