Mai intai trebuie sa te autentifici.
Cod sursa(job #2133599)
Utilizator | Data | 17 februarie 2018 10:25:12 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int urm[100000],lgmax[100000],V[100000];
int i,j,n,max1,incepmax;
int main()
{
fin>>n;
for (i=1;i<=n;i++)
fin>>V[i];
urm[n]=-1;
for (i=n;i>0;i--)
{
lgmax[i]=1;
urm[i]=-1;
for (j=i+1;j<=n;j++)
{
if (V[j]>V[i]&&lgmax[j]+1>lgmax[i])
{
lgmax[i]=lgmax[j]+1;
urm[i]=j;
}
}
}
for (i=1;i<=n;i++)
if (max1<lgmax[i])
{
max1=lgmax[i];
incepmax=i;
}
fout<<max1<<"\n";
while (incepmax!=-1)
{
fout<<V[incepmax]<<" ";
incepmax=urm[incepmax];
}
fout<<"\n";
return 0;
}