Pagini recente » Cod sursa (job #3279587) | Cod sursa (job #3279578) | Cod sursa (job #3162211) | Borderou de evaluare (job #3272912) | Cod sursa (job #1974303)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int NLIM = 1e5 + 10;
int N;
int v[NLIM];
int dp[NLIM];
int el[NLIM];
int eridx = 0;
int main()
{
fin >> N;
for( int i = 1; i <= N; ++i )
fin >> v[i];
dp[0] = 0;
for( int i = 1; i <= N; ++i )
{
int hmax = 0;
int hidx = 0;
for( int j = i - 1; j >= 0; --j )
{
if( v[i] > v[j] && dp[j] > dp[hidx] )
{
hidx = j;
}
}
dp[i] = dp[hidx] + 1;
el[i] = hidx;
//cout << i << ": " << dp[i] << " " << el[i] << "\n";
if( dp[i] > dp[eridx] )
{
eridx = i;
}
}
stack< int > res;
int hi = eridx;
while( res.size() < dp[eridx] )
{
res.push( v[hi] );
hi = el[hi];
}
fout << dp[eridx] << "\n";
while( res.size() )
{
fout << res.top() << " ";
res.pop();
}
fout << "\n";
return 0;
}