Pagini recente » Cod sursa (job #444126) | Cod sursa (job #1222706) | Cod sursa (job #2934676) | Cod sursa (job #1931182) | Cod sursa (job #2285961)
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std ;
ifstream f ("scmax.in");
ofstream g("scmax.out") ;
long long v[NMAX] , L[NMAX] , sol[NMAX] , lmax = 0 , q , N , Max , poz;
int main()
{
f >> N ;
for (int i = 1 ; i <= N ; i++)
f >> v[i] ;
L[1] = 1;
lmax = 1 ;
for (int i = 2 ; i <= N ; i ++)
{
Max = 0 ;
for (int j = i - 1 ; j >= 1 ; --j)
if (v[j] < v[i] && L[j] > Max)
Max = L[j];
L[i] = Max + 1 ;
if (L[i] > lmax)
{
lmax = L[i] ;
poz = i ;
}
}
q = 1 ;
sol[1] = v[poz];
lmax -- ;
for (int i = poz - 1 ; i >= 1 ; i -- )
{
if (v[i] < sol[q] && L[i] == lmax)
{
q++ ;
sol[q] = v[i];
lmax -- ;
}
}
g << q << '\n';
for (int i = q ; i >= 1 ; i--)
g << sol[i] << " " ;
return 0 ;
}