Cod sursa(job #639272)
#include <iostream>
#include <fstream>
using namespace std;
#define DIM 1000000
int a[DIM], prev[DIM], len[DIM];
ifstream f("scmax.in");
ofstream g("scmax.out");
void print(int pos)
{
if (pos < 0)
return;
if (pos != prev[pos])
print(prev[pos]);
g << a[pos] << " ";
}
int main()
{
int n, i, j, max, pos;
f >> n;
for (i = 0; i < n; i++)
f >> a[i];
len[0] = 1;
prev[0] = -1;
for (i = 1; i < n; i++) {
max = 0;
pos = i;
for (j = i - 1; j >= 0; j--) {
if (a[j] < a[i] && len[j] > max) {
max = len[j];
pos = j;
}
}
len[i] = 1 + max;
prev[i] = pos;
}
max = 0;
for (i = 0; i < n; i++)
if (len[i] > max) {
max = len[i];
pos = i;
}
g << max << endl;
print(pos);
f.close();
g.close();
}