Pagini recente » Cod sursa (job #1992659) | Cod sursa (job #1939485) | Cod sursa (job #1499555) | Cod sursa (job #3163468) | Cod sursa (job #2812341)
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n, x[100001], dp[100001], pre[100001];
void read()
{
in >> n;
for(int i = 1; i <= n; ++i)
in >> x[i];
}
int best(int k)
{
int b = 0;
for(int i = k + 1; i <= n; ++i)
if(x[k] < x[i] && dp[i] > b)
b = dp[i], pre[k] = i;
return b + 1;
}
void afis()
{
int sol = 0, p;
for(int i = 1; i <= n; ++i)
if(sol < dp[i])
sol = dp[i], p = i;
out << sol << '\n';
while(sol--)
{
out << x[p] << ' ';
p = pre[p];
}
}
int main()
{
read();
dp[n] = 1;
for(int i = n-1; i > 0; --i)
dp[i] = best(i);
afis();
return 0;
}