Pagini recente » oni2011_9 | Cod sursa (job #1460542) | Cod sursa (job #2876048) | Cod sursa (job #111533) | Cod sursa (job #1420775)
#include <fstream>
#include <string.h>
#define SZ 100010
using namespace std;
int max(int a, int b) {
return a > b ? a : b;
}
int best[SZ], preve[SZ], val[SZ];
int N;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main() {
memset(best, 1, SZ);
fin >> N;
int maxIndex = 0;
int maxBest = 0;
for (int i = 1; i <= N; ++i) {
fin >> val[i];
for (int j = 1; j < i; ++j) {
if (val[j] < val[i] && 1 + best[j] > best[i]) {
best[i] = 1 + best[j];
preve[i] = j;
}
}
if (best[i] > maxBest) {
maxBest = best[i];
maxIndex = i;
}
}
int count = 0;
int u = maxIndex;
while (u != 0) {
best[SZ - 1 - count] = val[u];
u = preve[u];
++count;
}
fout << count << '\n';
for (int i = 1; i <= count; ++i) {
fout << best[SZ - 1 - count + i] << ' ';
}
fout << '\n';
return 0;
}