Pagini recente » Cod sursa (job #819814) | Cod sursa (job #938533) | Cod sursa (job #1786957) | Cod sursa (job #1805502) | Cod sursa (job #2610951)
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
///Varianta o(n^2)
int n, a[nmax], lis[nmax], sol[nmax], nsol;
void Citire()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
}
void Rezolvare()
{
int i, j, mx;
lis[1] = 1;
for (i = 2; i <= n; i++)
{
mx = 0;
for (j = 1; j < i; j++)
if (a[j] < a[i] && mx < lis[j])
mx = lis[j];
lis[i] = 1 + mx;
}
mx = 0;
for (i = 1; i <= n; i++)
mx = max(mx, lis[i]);
fout << mx << "\n";
for (i = n; i >= 1; i--)
if (lis[i] == mx)
{
sol[++nsol] = a[i];
mx--;
}
for (i = nsol; i >= 1; i--)
fout << sol[i] << " ";
}
int main()
{
Citire();
Rezolvare();
return 0;
}