Cod sursa(job #639264)
#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)
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] = 0;
for (i = 1; i < n; i++) {
max = 0;
pos = i;
for (j = i - 1; j >= 0; j--) {
if (a[j] < a[i] && a[j] > max) {
max = a[j];
pos = j;
}
}
len[i] = 1 + len[pos];
prev[i] = pos;
}
max = 0;
for (i = 0; i < n; i++)
if (len[i] > len[max]) {
max = len[i];
pos = i;
}
g << max << endl;
print(pos);
f.close();
g.close();
}