Pagini recente » Cod sursa (job #1019580) | Cod sursa (job #1297168) | Cod sursa (job #460094) | Cod sursa (job #246951) | Cod sursa (job #1025387)
// 70 p pe infoarena, doar pentru ilustrarea programarii dinamice
#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; // initializare
for (i = n-1; i >= 1; i--) { // pentru fiecare element din sir
ml = 0; // initializarea maximului
for (j = i+1; j <= n; j++) // pentru fiecare element din dreapta elementului curent
if (a[j] > a[i] 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 i, is;
fo << lmax << endl; // Afisam lungimea maxima.
is = imax;
for (i = is; i <= n; i++) // pentru indicii potriviti
if ((a[i] >= a[is]) and (lmax == l[i])) { // Suntem la urmatorul element din subsirul cautat?
fo << a[i] << ' '; // Scriem elementul.
lmax--; // Raman de determinat mai putine elemente.
is = i; // Pregatim indicele pentru pasul urmator.
}
}
int main() {
citeste();
dinamic();
maxim();
scrie();
return 0;
}