Question

Наибольшая возрастающая подпоследовательность

У вас есть массив чисел длиною "N". Нужно найти следующую длину наибольшей возрастающей подпоследовательности. Ниже приведены несколько примеров

[1,3,5,4,7] => 3

[2,2,2,2,2] => 1

Входные данные:

(1 ≤ n ≤ 10000), где каждый элемент в массиве в промежутке (-10000 ≤ a[i] ≤ 10000)

Выходные данные:

Нужно найти следующую длину наибольшей возрастающей подпоследовательности.

Пример 1

Ввод:

8 86 62 91 22 59 71 46 100

Вывод:

3
​

Answer 1

Ответ:

#include <iostream>

#include <ctime>

int main()

{

   srand(time(NULL));

   int size = 0;

   while (size < 1 || size > 10000)

   {

       std::cout << "Enter size of the array: ";

       std::cin >> size;

   }

   

   int* arr = new int[size];

   

   for (int i = 0; i < size; i++)

   {

       arr[i] = -10000 + rand() % 20001;

       std::cout << arr[i] << " ";

   }

   int counter = 1, inRow = 1;

   for (int i = 0; i < size - 1; i++)

   {

       if (arr[i] < arr[i + 1])

       {

           inRow++;

       } else

       {

           if (inRow > counter) counter = inRow;

           inRow = 1;

       }

   }

   

   std::cout << "\nResult: " << counter << std::endl;

   

   delete[] arr;

}

Объяснение: C++