Cod sursa(job #3221190)
Utilizator | Daescu Gabriel Florin Gabriel_Daescu | Data | 6 aprilie 2024 11:22:50 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.78 kb |
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int N,i,j,l,lmax,L,st,dr,p,q,b[100002],c[100002];
long long v[100002];
int main()
{
fin>>N;
for(i=1; i<=N; i++)
{
fin>>v[i];
}
for(i=N; i>=1; i--)
{
lmax=0;
p=0;
for(j=i+1; j<=N; j++)
{
if(v[i]<v[j] && b[j]>lmax)
{
lmax=b[j];
p=j;
}
}
b[i]=1+lmax;
c[i]=p;
}
L=0;
for(i=1; i<=N; i++)
{
if(b[i]>L)
{
L=b[i];
q=i;
}
}
fout<< L << "\n";
for(i=q; i!=0; i=c[i])
{
fout<< v[i] << " ";
}
return 0;
}