Программа Php для поиска самой длинной последовательности Bitonic

Для заданного массива arr[0 … n-1], содержащего n положительных целых чисел, подпоследовательность arr[] называется Bitonic, если она сначала увеличивается, а затем уменьшается. Напишите функцию, которая принимает массив в качестве аргумента и возвращает длину самой длинной битовой последовательности.
Последовательность, отсортированная по возрастанию, считается битонической, а убывающая часть — пустой. Точно так же последовательность в порядке убывания считается битонической, а возрастающая часть считается пустой.
Примеры:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

Источник: вопрос интервью Microsoft.

Решение
Эта задача является разновидностью стандартной задачи о самой длинной возрастающей подпоследовательности (LIS). Пусть входной массив представляет собой массив arr[] длины n. Нам нужно построить два массива lis [] и lds [], используя решение задачи LIS с помощью динамического программирования. lis[i] хранит длину самой длинной возрастающей подпоследовательности, заканчивающейся на arr[i]. lds[i] хранит длину самой длинной убывающей подпоследовательности, начиная с arr[i]. Наконец, нам нужно вернуть максимальное значение lis[i] + lds[i] – 1, где i находится в диапазоне от 0 до n-1.
Ниже приведена реализация вышеупомянутого решения динамического программирования.

Выход:

 Length of LBS is 7

Временная сложность: O(n^2)
Вспомогательное пространство: O(n)

Пожалуйста, обратитесь к полной статье о самой длинной битонической последовательности | DP-15 для более подробной информации!