Pagini recente » Cod sursa (job #1700676) | Cod sursa (job #1897699) | Cod sursa (job #1180785) | Cod sursa (job #839862) | Cod sursa (job #2109424)
#include <bits/stdc++.h>
#define in "scmax.in"
#define out "scmax.out"
#define nmax 100003
using namespace std;
ifstream fin(in);
ofstream fout(out);
int n;
int a[nmax];
int dp[nmax];
int urm[nmax];
void Read()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
}
void Dyn()
{
int i,j;
int maxim,poz;
dp[n] = 1;
urm[n] = n+1;
for (i = n-1; i >= 1; i--)
{
maxim = 0; poz = n+1;
for (j = i+1; j <= n; j++)
if (a[j] > a[i] && maxim < dp[j])
{
maxim = dp[j];
poz = j;
}
dp[i] = 1 + maxim;
urm[i] = poz;
}
poz = 1;
for (i = 2; i <= n; i++)
if (dp[i] > dp[poz]) poz = i;
fout << dp[poz] << "\n";
while (poz != n+1)
{
fout << a[poz] << " ";
poz = urm[poz];
}
}
int main()
{
Read();
Dyn();
fin.close();
fout.close();
return 0;
}