Cod sursa(job #2491047)
| Utilizator | Data | 11 noiembrie 2019 18:38:15 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 10 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{ int k,MAX=0,imax;
fin>>k;
int v[k],lmax[k],succ[k];
lmax[k-1]=1;
succ[k-1]=-1;
for(int i=0;i<k;i++) fin>>v[i];
for(int i=k-2;i>=0;i--)
{
int ll=0,jj=0;
for(int j=i+1;j<k;j++)
if(v[j]>v[i])
if(ll<lmax[j]){ll=lmax[j];jj=j;}
succ[i]=jj;
lmax[i]=ll+1;
if(MAX<lmax[i]) MAX=lmax[i],imax=i;
}
fout<<MAX<<'\n';
int p=imax;
while(p!=-1)
{ fout<<v[p]<<" ";
p=succ[p];
}
return 0;
}
