Pagini recente » Autentificare | Cod sursa (job #3193610) | Cod sursa (job #2870711) | Cod sursa (job #2254404) | Cod sursa (job #2870443)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=1e5;
int v[N+5],dp[N+5],poz[N+5];
int main()
{
int n; in>>n;
for(int i=1;i<=n;i++) in>>v[i];
dp[1]=1,poz[1]=1;
int lungMAX=-1,pozMAX=0;
for(int i=2;i<=n;i++) //dp[i] = 1 + max(dp[j] | v[i]>v[j], 0 < j < i)
{
int lung=0,pz=0;
for(int j=1;j<i;j++)
if(v[j]<v[i] && dp[j] > lung) lung=dp[j],pz=poz[j];
dp[i]=1+lung;
if(!pz) poz[i]=i;
else poz[i]=pz;
if(dp[i] > lungMAX) lungMAX=dp[i],pozMAX=poz[i];
}
out<<lungMAX<<'\n';
int anterior=v[pozMAX];
for(int i=pozMAX+1,j=1;j<lungMAX;i++)
if(v[i] > anterior)
{
out<<anterior<<' ';
anterior=v[i];
j++;
}
out<<anterior;
return 0;
}