Cod sursa(job #2386194)
Utilizator | Data | 22 martie 2019 12:37:10 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.76 kb |
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,i,maxim,p,j,u,k,v[100002],t[100002],d[100002],af[100002];
int main()
{
fin >> n;
for (i=1;i<=n;i++)
{
fin >> v[i];
}
n++;
v[n]=2000000005;
d[1]=1;
for (i=2;i<=n;i++)
{
maxim=0;
p=0;
for (j=1;j<i;j++)
{
if (v[j]<v[i] && d[j]>maxim)
{
maxim=d[j];
p=j;
}
}
d[i]=maxim+1;
t[i]=p;
}
u=t[n];
while (u!=0)
{
k++;
af[k]=v[u];
u=t[u];
}
fout << k << "\n";
for (i=k;i>=1;i--) fout << af[i] << " ";
return 0;
}