Pagini recente » Cod sursa (job #1227075) | Cod sursa (job #1998883) | Cod sursa (job #1264618) | Cod sursa (job #1444178) | Cod sursa (job #1321479)
#include <fstream>
using namespace std;
ifstream fi("scmax.in");
ofstream fo("scmax.out");
int l[100001], a[100001], n, lmax, imax;
void citeste () {
int i;
fi >> n;
for (i = 1; i <= n; i++)
fi >> a[i];
}
void dinamic () {
int ml, i, j;
// ml - maximul lungimilor subsirurilor crescatoare care incep dupa pozitia "i" cu un element > a[i]
l[n] = 1;
for (i = n - 1; i >= 1; i--) {
ml = 0;
for (j = i + 1; j <= n; j++) // pentru fiecare element din dreapta elementului curent
if (a[i] < a[j] and l[j] > ml) // Sunt indeplinite conditiile?
ml = l[j]; // Actualizam maximul lungimilor subsirurilor care incep dupa elementul curent.
l[i] = ml + 1; // lungimea celui mai lung subsir care incepe pe locul i
}
}
void maxim () {
int i;
lmax = l[1]; imax = 1;
for (i = 1; i <= n; i++)
if (l[i] > lmax) {
lmax = l[i]; imax = i;
}
}
void scrie() {
int is, id;
fo << lmax << endl; // Afisam lungimea maxima.
fo << a[imax] << ' '; // primul element din subsir
for (is = imax, id = is + 1; l[is] > 1; id++)
if (a[is] < a[id] and l[id] == l[is] - 1) {
fo << a[id] << ' ';
is = id;
}
}
int main() {
citeste();
dinamic();
maxim();
scrie();
return 0;
}