8b_max_nenamalqvashta_redica

#include <iostream>
using namespace std;
#define MAX 1000000

int x[MAX]; /* Редица */
/* Нулевият елемент на x[] не се използва! */
unsigned n; /* Брой елементи в редицата */
int LNS[MAX]; /* LNS[i] - минимален елемент, който може да стои на позиция i */

/* Намира дължината на най-дългата ненамаляваща подредица */
unsigned LNS_Length(void)
{ unsigned i, r, k, l, med;

  for (LNS[1] = x[1], k = 1, i = 2; i <= n; i++) {
    if (x[i] < LNS[1])        /* случай 1 */
      LNS[1] = x[i];
    else if (x[i] >= LNS[k])  /* случай 2 */
      LNS[++k] = x[i];
    else {                    /* случай 3 */
      l = 1;
      r = k;                  /* двоично търсене */
      while (l < r - 1) {
        med = (l + r) / 2;
        if (LNS[med] <= x[i])
          l = med;
        else
          r = med;
      }
      LNS[r] = x[i];
    }
  }
  return k;
}

int main(void) {
    int ind=1;
    while ( cin >> n ){
        for( int i=1; i<=n; i++ ) cin >> x[i];
        cout << LNS_Length() << endl;
    }
  return 0;
}
/*
Задача 8b. [8.2.7] lns3.c
Да се напише програма за намиране на най-дългата ненамаляваща подредица.

 Вход:
На входа се задава числото n - брой на елемнтите на редицата  и след това стойностите на самите елементи - цели числа в интервала
[-10, 105].  Входът съдържа много примери.

 Изход:
 За всеки пример на отделен ред се отпечатва цяло число - дължината на най-дългата ненамаляваща подредица.

 Пример:
6
 6 6 6 2 2 7
 6
 1 1 1 1 1 2
 15
 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
 3
 4 3 2

Решение на примера:
4
 6
 8
1

 Редиците са: 6 6 6 7; 1 1 1 1 1 2; 1 2 2 2 2 2 2 2 (има и друга); 4.
*/