Pagini recente » Cod sursa (job #1975319) | Cod sursa (job #592223) | Borderou de evaluare (job #978022) | Cod sursa (job #1795180) | Cod sursa (job #3261820)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5 + 1;
int N, ans, ansPos;
int v[N_MAX];
int dp[N_MAX], t[N_MAX];
void SetInput(string name)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
(void)!freopen((name + ".in").c_str(), "r", stdin);
(void)!freopen((name + ".out").c_str(), "w", stdout);
}
void ReadArray()
{
cin >> N;
for(int i = 1; i <= N; i++)
cin >> v[i];
}
void DisplayPath(int p)
{
if(t[p] != 0)
DisplayPath(t[p]);
cout << v[p] << ' ';
}
void Solve()
{
dp[1] = 1;
t[1] = 0;
for(int i = 2, j, mx, p; i <= N; i++)
{
mx = 0;
p = 0;
for(j = 1; j < i; j++)
if(v[j] < v[i] && dp[j] > mx)
{
mx = dp[j];
p = j;
}
dp[i] = mx + 1;
if(dp[i] == 1)
t[i] = 0;
else
t[i] = p;
if(dp[i] > ans)
{
ans = dp[i];
ansPos = i;
}
}
cout << ans << '\n';
DisplayPath(ansPos);
}
int main()
{
SetInput("scmax");
ReadArray();
Solve();
return 0;
}