Pagini recente » Cod sursa (job #2981528) | Cod sursa (job #2824147) | Cod sursa (job #1260952) | Cod sursa (job #3267914) | Cod sursa (job #2760705)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, a[100005], dp[100005], ans[100005];
void citire()
{
fin >> n;
for(int i = 1; i <= n; i ++)
fin >> a[i];
}
void solve()
{
int poz = 1;
for(int i = 1; i <= n; i ++)
{
dp[i] = 1;
for(int j = 1; j < i; j ++)
{
if(a[j] < a[i])
{
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
for(int i = 1; i <= n; i ++)
{
if(dp[i] > dp[poz])
poz = i;
}
fout << dp[poz] << '\n';
int k = 0;
ans[++k] = a[poz];
for(int i = poz - 1; i >= 1; i --)
{
if(a[i] < a[poz] && dp[i] == dp[poz] - 1)
{
poz = i;
ans[++k] = a[i];
}
}
for(int i = k; i >= 1; i --)
fout << ans[i] << ' ';
}
int main()
{
citire();
solve();
return 0;
}