Самая длинная возрастающая подпоследовательность в данном связанном списке

Опубликовано: 19 Сентября, 2022

Дана последовательность чисел в виде связанного списка lis . Найдите длину самой длинной возрастающей подпоследовательности (LIS) данного связанного списка.

Примеры:

Input:  list = 3->10->2->1->20
Output: 3
Explanation: The longest increasing subsequence is 3->10-> 20

Input:  list = 3-> 2
Output: 1
Explanation: The longest increasing subsequence are 3 and 2

Input: list = 50->3->10->7->40->80
Output: Length of LIS = 4
Explanation: The longest increasing subsequence is {3->7->40->80} or {3->10->40->80}

Подход: основная интуиция решения состоит в том, чтобы начать итерацию от первого узла до конца связанного списка. В процессе перемещения вычислите длину LIS, заканчивающуюся в каждом узле, и сохраните ее в переменной count . Наконец, вычислите максимальное значение счетчика среди всех узлов. Выполните шаги, указанные ниже, чтобы решить проблему:

  • Пройдите по связанному списку от начального узла.
    • Длина LIS связанного списка с одним узлом равна 1 . Поэтому мы инициализируем каждую переменную счетчика узлов значением 1 .
    • Для каждого i -го узла обойдите первые (i-1) узлы и выполните следующие действия:
      • если значение текущего узла больше значения предыдущего узла, удлинить длину последовательности .
      • Поскольку требуется максимальная длина, заканчивающаяся текущим узлом. выберите узел из первых (i-1) узлов, которые удовлетворяют предыдущему условию и иметь максимальное значение счета.
  • Как только все узлы пройдены в соответствии с описанной выше процедурой, найдите максимальное значение счетчика среди всех узлов.
  • Максимальное значение счетчика — это необходимая длина LIS .

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N * N), где N — длина связанного списка.
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ