Pagini recente » Cod sursa (job #2345988) | Cod sursa (job #2808137) | Cod sursa (job #1948601) | Cod sursa (job #2315153) | Cod sursa (job #1319908)
#include <fstream>
const int lg=100005;
using namespace std;
ifstream in("scmax.in");
ofstream out ("scmax.out");
int dp[lg], v[lg], pred[lg], sol[lg];
int n;
int main()
{
int i, j;
in>>n;
dp[1]=1;
pred[1] = 0;
for(i=1; i<=n; ++i)
in>>v[i];
int poz, maxim;
for(i=2; i<=n; ++i)
{
maxim = 0;
poz = 0;
for(j=1; j<i; ++j)
if(v[j]<v[i] && dp[j] > maxim)
{
maxim = dp[j];
poz = j;
}
dp[i] = maxim + 1;
pred[i] = poz;
}
poz, maxim = 0;
for (i = 1; i <= n; ++ i)
if (dp[i] > maxim)
{
maxim = dp[i];
poz = i;
}
out << maxim <<"\n";
i = 1;
while (poz != 0)
{
sol[i] = poz;
poz = pred[poz];
i++;
}
for (j = i - 1; j >= 1; -- j)
out << v[sol[j]] << " " ;
return 0;
}