Pagini recente » Cod sursa (job #755245) | Cod sursa (job #2378894) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2261346)
#include <fstream>
#define NMAX 100010
std::ifstream fin("scmax.in");
std::ofstream fout("scmax.out");
int n;
int a[NMAX];
int lis[NMAX];
int prec[NMAX];
int main() {
int i, j;
int lisMax, posMax;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
lisMax = -1;
for (i = n; i >= 1; i--) {
lis[i] = 1;
prec[i] = 0;
for (j = i + 1; j <= n; j++)
if (a[i] < a[j] && lis[j] + 1 > lis[i]) {
lis[i] = lis[j] + 1;
prec[i] = j;
}
if (lis[i] > lisMax) {
lisMax = lis[i];
posMax = i;
}
}
fout << lisMax << '\n';
for (i = posMax; i <= n && lisMax; i++)
if (lis[i] == lisMax) {
lisMax--;
fout << a[i] << ' ';
}
fout.close();
return 0;
}