Cod sursa(job #788117)
Utilizator | Data | 14 septembrie 2012 10:31:24 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100001],x[100001],i,n,st,dr,s,mij;
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
s=1;
for(i=2;i<=n;i++)
{
st=1;
dr=s;
while(st<=dr)
{
mij=(st+dr)/2;
if(a[i]>a[x[mij]])
st=mij+1;
else
dr=mij-1;
}
if(st>s)
s++;
x[s]=i;
}
g<<s-1<<"\n";
for(i=2;i<=s;i++)
g<<a[x[i]]<<" ";
return 0;
}