Pagini recente » Cod sursa (job #2068360) | Cod sursa (job #31245) | Cod sursa (job #2933040) | Cod sursa (job #20548) | Cod sursa (job #1185719)
#include <cstdio>
#include <cstring>
#define MAXN 100005
int n;
int a[MAXN];
// d[i] - cel mai lung subsir din primele i elemente
int best[MAXN];
int pre[MAXN];
void get_max(int n, int* max, int* p)
{
*max = 0;
*p = 0;
for (int i = 1; i < n; i++) {
if (a[i] < a[n] && best[i] > *max) {
*max = best[i];
*p = i;
}
}
}
void solve()
{
int max, p;
for (int i = 1; i <= n; i++) {
get_max(i, &max, &p);
best[i] = 1 + max;
pre[i] = p;
}
}
void print_helper(int p)
{
if (p == 0)
return;
print_helper(pre[p]);
printf("%d ", a[p]);
}
void print()
{
int max = 0;
int p = 0;
for (int i = 1; i < n; i++) {
if (best[i] > max) {
max = best[i];
p = i;
}
}
printf("%d\n", max);
print_helper(p);
}
int main()
{
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
solve();
print();
return 0;
}