Pagini recente » Cod sursa (job #2270990) | Cod sursa (job #90007) | Cod sursa (job #1607693) | Cod sursa (job #1663517) | Cod sursa (job #1024922)
// 70 p pe infoarena, doar pentru ilustrarea programarii dinamice
#include <fstream>
using namespace std;
ifstream fi("grader_test1.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++)
if (a[j] > a[i] 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; 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;
}