Pagini recente » Cod sursa (job #2184544) | Istoria paginii runda/cex_ph_4/clasament | Cod sursa (job #948634) | Cod sursa (job #1773139) | Cod sursa (job #1854757)
#include <fstream>
#define nmax 100001
using namespace std;
ifstream fin ( "scmax.in" );
ofstream fout ( "scmax.out" );
int a[nmax], lg[nmax], t[nmax], sol[nmax];
int main()
{ int n, i, m, j;
int lgmax, imax;
fin >> n;
for ( i = 1; i <= n; i++ )
fin >> a[i];
fin.close();
lg[1] = 1;
t[1] = 0;
for ( i = 2; i <= n; i++ )
{ lg[i] = 1;
t[i] = 0;
for ( j = 1; j <= i - 1; j++ )
if ( a[j] < a[i] && lg[j] + 1 > lg[i] )
{ lg[i] = lg[j] + 1;
t[i] = j;
}
}
lgmax = 0;
for ( i = 1; i <= n; i++ )
if ( lg[i] > lgmax )
{ lgmax = lg[i];
imax = i;
}
m = 1;
sol[1] = a[imax];
while ( t[imax] )
{ imax = t[imax];
m++;
sol[m] = a[imax];
}
fout << lgmax << "\n";
for ( i = m; i >= 1; i-- )
fout << sol[i] << " ";
fout << "\n";
fout.close();
return 0;
}