Mai intai trebuie sa te autentifici.
Cod sursa(job #896150)
| Utilizator | Data | 27 februarie 2013 14:01:33 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.83 kb |
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int maxn = 100001;
int M[maxn], P[maxn], v[maxn], N, nr;
void afis(int ind)
{
if (P[ind] > 0) afis(P[ind]);
out << v[ind] << ' ';
}
int caut(int x)
{
int p, u, m;
p = 0; u = nr; m = (p+u)/2;
while (p <= u)
{
if (v[M[m]] < x && v[M[m+1]] >= x) return m;
else if (v[M[m+1]] < x) {p = m + 1; m = (p + u)/2;}
else {u = m - 1; m = (p + u)/2;}
}
return nr;
}
int main()
{
in >> N; int j;
for (int i = 1; i <= N; i++) in >> v[i];
M[1] = 1; M[0] = 0; nr = 1;
for (int i = 2; i <= N; i++)
{
j = caut(v[i]);
P[i] = M[j];
M[j+1] = i;
if (nr < j+1) nr = j+1;
}
out << nr << '\n';
afis(M[nr]);
return 0;
}
