Cod sursa(job #850907)
Utilizator | FMI Alex Oprea BlackLord | Data | 9 ianuarie 2013 08:26:26 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.72 kb |
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n, v[100010], b[100010], m, p, u, i, nr, a[100010];
void afisare(int x){
if(x)
{
afisare(a[x]);
g<<v[x]<<' ';
}
}
int main(){
f>>n;
for(i=1; i<=n; i++)
f>>v[i];
f.close();
b[1]=1;
nr=1;
for(i=2; i<=n; i++)
{
p=1;
u=nr;
while(p<=u)
{
m=(u-p)/2+p;
if(v[i]>v[ b[m] ])
p=m+1;
else
u=m-1;
}
if(p>nr)
nr++;
b[p]=i;
a[i]=b[p-1];
}
g<<nr<<"\n";
afisare(b[nr]);
g.close();
return 0;
}