Pagini recente » Cod sursa (job #2566612) | Cod sursa (job #1076659) | Cod sursa (job #1752438) | Cod sursa (job #528288) | Cod sursa (job #1420772)
#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], prev[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];
prev[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 = prev[u];
++count;
}
fout << count << '\n';
for (int i = 1; i <= count; ++i) {
fout << best[SZ - 1 - count + i] << ' ';
}
fout << '\n';
return 0;
}