Pagini recente » Cod sursa (job #2438305) | Cod sursa (job #1456009) | Cod sursa (job #2828820) | Cod sursa (job #1541637) | Cod sursa (job #2670406)
#include <bits/stdc++.h>
using namespace std;
int lscmax, lmax, pozmax,elemmax, n, x, k, maxim, dp[100005];
int V[100005];
vector <int> F;
void fast ()
{
ios_base::sync_with_stdio(false);
cin.tie();
}
int main()
{
fast();
freopen("scmax.in","r", stdin);
freopen("scmax.out","w", stdout);
cin >> n;
for (int i=1; i<=n; i++)
{
cin >> x;
V[i]=x;
}
/// cazul de baza
dp[1]=1;
for (int i=2; i<=n; i++)
{
for (int j=1; j<i; j++)
{
if (V[j]<V[i])
{
maxim = max (maxim, dp[j]);
}
}
/// dp[i] cel mai lung subsir care se termina in elementul i; incep dp[2]
dp[i] = maxim + 1;
if (dp[i]>lmax)
{
lmax=dp[i];
pozmax=i;
elemmax=V[i];
}
}
F.push_back(elemmax);
lscmax=dp[n];
cout << lscmax << endl;
for (int i=pozmax; i>=1; i--)
if (elemmax>V[i-1] && lscmax>1)
{
F.push_back(V[i-1]);
lscmax--;
elemmax=V[i-1];
}
for (int i=(int)F.size()-1; i>=0; i--)
cout << F[i] << " ";
return 0;
}