Pagini recente » Cod sursa (job #1039891) | Cod sursa (job #2346397) | Cod sursa (job #1218865) | Cod sursa (job #2874803) | Cod sursa (job #2823485)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
const int NMAX = 100003;
int best[NMAX], a[NMAX], maxi, sol = 0, poz[NMAX], p;
int n;
void read()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> a[i];
}
}
void dp()
{
int i,j;
best[n] = 1;
poz[n] = -1;
maxi = 1;
p = n;
for (i = n; i >= 1; --i)
{
best[i] = 1;
poz[i]=-1;
for (j = i+1; j <= n; ++j)
{
if (a[i]<a[j] && best[i]<best[j]+1)
{
best[i] = best[j] + 1;
poz[i] = j;
if (best[i] > maxi)
{
maxi = best[i];
p = i;
}
}
}
}
}
void constr()
{
int i;
i = p;
while (i != -1)
{
fout << a[i] << ' ';
i = poz[i];
}
}
int main()
{
read();
dp();
fout << maxi << '\n';
constr();
return 0;
}