Pagini recente » Cod sursa (job #1343526) | Cod sursa (job #2553914) | Cod sursa (job #1086226) | Cod sursa (job #247694) | Cod sursa (job #2274425)
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int LIS[100005],PREi[100005],n,v[100005],p,maxim;
int main()
{
int i,j;
fin>>n;
for(i=1;i<=n;i++) fin>>v[i];
LIS[n]=1;
PREi[n]=-1;
maxim=1;
p=n;
for(i=n-1;i>=1;--i)
{
LIS[i]=1;
PREi[i]=-1;
for(j=i+1;j<=n;++j)
if(v[i]<v[j] && LIS[i]<LIS[j]+1)
{
LIS[i]=LIS[j]+1;
PREi[i]=j;
if(LIS[i]>maxim) maxim=LIS[i],p=i;
}
}
fout<<maxim<<'\n';
i=p;
while(i!=-1)
{
fout<<v[i]<<' ';
i=PREi[i];
}
return 0;
}