Cod sursa(job #1361128)
Utilizator | Data | 25 februarie 2015 19:48:21 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 65 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
#include <algorithm>
using namespace std;
int n, i, a[100001], q[100001], m, poz;
int main()
{
ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for(i=1; i<=n; i++)
{
f>>a[i];
}
q[1]=a[1];
m=1;
for(i=2; i<=n; i++)
{
poz=lower_bound(q, q+m+1, a[i])-q;
if(poz>m)
{
m++;
q[m]=a[i];
}
else
{
q[poz]=a[i];
}
}
g<<m<<"\n";
for(i=1; i<=m; i++)
{
g<<q[i]<<" ";
}
}