Pagini recente » Cod sursa (job #101734) | Cod sursa (job #2918668) | Cod sursa (job #2694771) | Cod sursa (job #1920921) | Cod sursa (job #2870114)
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#define NMAX 100001
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,v[NMAX];
void Citire()
{
f>>n;
for(int i=1;i<=n;i++)
f>>v[i];
}
void Rezolvare()
{
int maxi=0,fin,st;
vector <int> dp(n+1);
dp[1]=1;
maxi=dp[1];
st=1;
for(int i=2;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<=i-1;j++)
{
if(v[j]<v[i]&&dp[j]>=dp[i])
{
st=j-1;
dp[i]=dp[j]+1;
}
}
if(dp[i]>maxi)
{
maxi=dp[i];
fin=i;
}
}
int t=1;
g<<maxi<<'\n';
for(int i=fin-1;i>=1;i--)
{
if(v[i]<v[fin]&&dp[i]==dp[fin]-t)
{
st=i;
t++;
}
if(dp[st]==1)
break;
}
t=0;
for(int i=st;i<=fin;i++)
{
if(dp[i]==dp[st]+t)
{
g<<v[i]<<' ';
t++;
}
if(i==fin)
break;
}
}
int main()
{
Citire();
Rezolvare();
return 0;
}