Pagini recente » Cod sursa (job #2385177) | Cod sursa (job #497709) | Cod sursa (job #1081911) | Cod sursa (job #2432101) | Cod sursa (job #1024887)
// 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;
for (i = n-1; i >= 1; i--) {
ml = 1;
for (j = i+1; j <= n; j++)
if (a[i] < a[j] and l[j] > ml)
ml = l[j];
l[i] = ml+1;
}
}
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, id;
fo << lmax << endl;
fo << a[imax] << ' ';
for (is = imax, id = is+1; id <= n; is = id, id++)
if (a[is] < a[id] and l[id] == l[is]-1)
fo << a[id] << ' ';
}
int main() {
citeste();
dinamic();
maxim();
scrie();
return 0;
}