Cod sursa(job #505487)
Utilizator | Farcas Ionut hunter_ionutzzz | Data | 2 decembrie 2010 18:37:46 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include<fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long i,j,x,max,n,v1[100000],v2[100000],v3[100000];
int main()
{ fin >> n;
for (i=1;i<=n;i++)
fin >> v1[i];
for (i=n-1;i>=1;i--)
{ for (j=i+1;j<=n;j++)
if (v1[i] < v1[j] && v2[i] < v2[j] + 1)
{ v2[i] = v2[j] + 1;
v3[i] = j;
if (v2[i] > max)
{ x = i;
max = v2[i];
}
}
}
fout << max+1 << '\n';
while (x != 0)
{ fout << v1[x] << " ";
x = v3[x];
}
return 0;
}