# PBinfo #1876 – SCLM2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Vlad și Alex sunt doi prieteni foarte buni. Aceștia sunt pasionați de jocuri și vor să vă propună unul: Se dau n numere naturale sub forma unui șir. Un subșir se numește “corect” dacă este ordonat crescător. Pentru a câștiga, jucătorul trebuie să ghicească lungimea maxima a unui astfel de subșir. Deoarece nu le place sa piardă, cei doi vă cer ajutorul.

Date de intrare
Fișierul de intrare sclm2.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire sclm2.out va conține pe prima linie numărul l, lungimea maximă a unui subșir “corect”.

Restricții și precizări

1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplu:
sclm2.in

7
3 1 4 3 5 6 9
sclm2.out

5
Explicație
Subșirul “corect” de lungime maxima este: 1 3 5 6 9 și are lungime 5.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
int sol[100001], k, n, p, put, r[100001];
void adaugare (int x)
{
    if (k == 0)
    {
        sol[k++] = x;
        return ;
    }
    if (x >= sol[k-1])
    {
        sol[k++] = x;
        return ;
    }
    if (x<sol[0])
    {
        sol[0] = x;
        return;
    }
    int p=1, put = 0, i, poz = 0;
    while (p<<1 <= k)
    {
        p = p<<1;
        ++put;
    }
    for (i = put; i>=0; --i)
    {
        if (poz + p < k && x >= sol[poz+p])
            poz+=p;
        p>>=1;
    }
    sol[poz+1] = x;
}
int main()
{
    ifstream fin ("sclm2.in");
    ofstream fout ("sclm2.out");
    int i, j = 0, x, copie;
    fin >> n;
    for (i = 0; i<n; ++i)
    {
        fin >> x;
        adaugare(x);
    }
    fout << k;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1876)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1876/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1876/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)