Самая длинная возрастающая подпоследовательность - O (n log n)

Учитывая массив случайных чисел, найдите самую длинную возрастающую подпоследовательность. Эта подпоследовательность не обязательно является смежной или уникальной. В этом уроке мы иллюстрируем решение динамического программирования (DP), которое работает в O (n log n). Два доказательства также представлены. Первое доказательство сделано по индукции. Во втором доказательстве используется тот факт, что алгоритм сортировки терпения сводит к минимуму количество стопок, и, поскольку каждая стопка содержит карты в порядке убывания, любая возрастающая последовательность может содержать не более одной карты из каждой стопки. Эта проблема программирования обычно задается во время технических / программных интервью в технических фирмах, таких как Google и Microsoft. Исходный код, реализованный на Java: https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/challenge/LongestIncreasingSubsequence.java Википедия: https://en.wikipedia.org/wiki/Longest_increasing_subsequence «Сортировка терпения» - это алгоритм сортировки общего назначения, который в процессе сортировки также находит самую длинную возрастающую подпоследовательность. Это видео объясняет, как сортировка терпения работает путем помещения чисел (игральные карты используются для иллюстрации) в стопки убывающих значений. Если мы также удерживаем указатель от размещенной карты до верхней части стопки непосредственно с левой стороны, создаются цепочки указателей, ведущие к самой левой стопке. Таким образом, в конце вы можете выбрать любую карту в правой правой стопке и следовать указателям на самую левую стопку, восстанавливая (или одну из) самую длинную увеличивающуюся последовательность в обратном порядке. Неформальное доказательство: Поскольку карты в стопке образуют убывающую последовательность, любая возрастающая последовательность может использовать не более одной карты из каждой стопки. Таким образом, независимо от того, какую стратегию вы используете для игры, количество стопок всегда ≥ длины любой увеличивающейся последовательности. Поскольку жадная стратегия «Сортировка терпения» сводит к минимуму количество куч, и каждая куча связана с помощью указателей, следование указателям дает нам самую длинную последовательность увеличения. Доказательство по индукции: Первая карта, назовем ее картой 1, помещается в стопку 1 и, очевидно, создает подпоследовательность длины 1. Это наш базовый случай. Для второго шага предположим, что после помещения n-й карты, карты-N, в стопку-K создается подпоследовательность длины K. Посмотрим, верно ли это для следующей карты, cardN + 1. Если карта N + 1 больше карты-N, она не будет помещена ни в одну стопку слева от стопки-K, поскольку жадная стратегия «Терпение терпения» поместила бы предыдущую карту, карту-N, в эту стопку вместо свая-K. И он не будет помещен в кучу К, так как правило игры «Терпение» не позволяет этого. Таким образом, cardN + 1 помещается в некоторую стопку справа, тем самым увеличивая длину ранее вычисленной подпоследовательности.