Pagini recente » Cod sursa (job #3001266) | Cod sursa (job #1024992) | Cod sursa (job #2433959) | Cod sursa (job #1939510) | Cod sursa (job #373795)
Cod sursa(job #373795)
#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++)
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;
fo << lmax << endl;
for (i = imax; i <= n; i++)
if ((a[i] >= a[imax]) and (lmax == l[i])) {
fo << a[i] << ' ';
lmax--;
}
}
int main() {
citeste();
dinamic();
maxim();
scrie();
return 0;
}