Cod sursa(job #1998394)
| Utilizator | Data | 7 iulie 2017 17:56:35 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 5 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.86 kb |
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{
int n, v[100001], lg[100001], low, high, mid, i;
lg[0]=0;
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i];
for (i=1;i<=n;i++)
{
if (v[i]>lg[lg[0]])
{
lg[++lg[0]]=v[i];
}
else
{
low=1;
high=lg[0];
mid=ceil((low+high)/2);
while (v[i]<lg[mid]||v[i]>lg[mid+1])
{if (v[i]<lg[mid])
high=mid;
else low=mid;
mid=ceil((low+high)/2);
}
lg[mid]=v[i];
}
}
fout<<lg[0]<<'\n';
for (i=1;i<=lg[0];i++)
fout<<lg[i];
return 0;
}
