Pagini recente » Cod sursa (job #1419110) | Cod sursa (job #2907803) | Cod sursa (job #1301895) | Cod sursa (job #3197732) | Cod sursa (job #1816387)
# include <cstdio>
# include <algorithm>
using namespace std;
FILE *f = freopen("scmax.in", "r", stdin);
FILE *g = freopen("scmax.out", "w", stdout);
const int N_MAX = 100010;
int v[N_MAX];
int l_max[N_MAX];
int prev_poz[N_MAX];
int n;
int maxim = 0;
int poz_maxim = 0;
void read()
{
scanf("%d", &n);
for (int i=1; i<=n; i++)
scanf("%d", &v[i]);
}
void solve()
{
l_max[n] = 1;
prev_poz[n] = -1;
for (int i=n-1; i>=1; i--)
{
int poz_max = 0;
for (int j=i+1; j<=n; j++)
{
if (v[j] > v[i])
{
if (l_max[j] + 1 > l_max[i])
{
poz_max = j;
l_max[i] = l_max[j] + 1;
}
}
}
if (poz_max == 0)
{
l_max[i] = 1;
prev_poz[i] = -1;
}
else
{
prev_poz[i] = poz_max;
}
if (l_max[i] > maxim)
{
maxim = l_max[i];
poz_maxim = i;
}
}
printf("%d\n", l_max[poz_maxim]);
while (prev_poz[poz_maxim] != -1)
{
printf("%d ", v[poz_maxim]);
poz_maxim = prev_poz[poz_maxim];
}
printf("%d ", v[poz_maxim]);
}
int main()
{
read();
solve();
return 0;
}