LeetCode 300. Самая длинная возрастающая подпоследовательность — Python Solution

Blind 75 — Вопросы по программированию и техническому интервью — серия объяснений

Проблема:

Объяснение:

Это всегда грубое решение с использованием поиска в глубину O (2 ^ n). Затем следует решение для динамического программирования O(n²). Это еще одно решение O(nlogn), которое я не буду объяснять, так как это сложное решение, и, вероятно, его не ожидают в интервью. Решение для динамического программирования работает с обратными словами от конца массива к началу. Причина этого в том, что для нескольких последних индексов легко вычислить, какова их самая длинная возрастающая подпоследовательность, но чем дальше вы уходите, тем сложнее.

Чтобы исправить это, если вы кэшируете решения, работающие в обратном порядке, вы можете использовать эти сохраненные вычисления, а не переделывать работу. Предостережение заключается в том, что вы не можете просто использовать ранее вычисленный LIS, потому что это может не привести к самой длинной возрастающей подпоследовательности. Чтобы решить эту проблему, вы должны просмотреть ВСЕ ранее рассчитанные LIS, чтобы найти лучшую подпоследовательность для этого конкретного значения, поэтому эта проблема равна O (n²). Теперь, чтобы определить эту подпоследовательность для каждой ранее рассчитанной LIS, вы устанавливаете текущую LIS на максимум самого себя и 1 плюс ранее рассчитанную LIS. Это гарантирует максимальную LIS для каждого индекса в массиве.

Решение для динамического программирования: O(n²)

Сначала инициализируйте массив для хранения LIS для каждого индекса, а затем начните перебирать все значения в обратном порядке. В этом цикле создайте еще один цикл, который идет от i+1 до последнего значения в массиве. Затем определите, можно ли добавить текущее значение в подпоследовательность LIS[j] (поскольку мы работаем в обратном направлении, оно должно быть меньше nums[j]). Если это так, то установите текущую LIS на максимум самой себя и 1 плюс LIS[j]. После циклов просто верните максимум списка. Супер простой код, но понятное объяснение.

class Solution:
 def lengthOfLIS(self, nums: List[int]) -> int:
  LIS = [1] * len(nums)
 
  for i in range(len(nums) — 1, -1, -1):
   for j in range(i + 1, len(nums)):
    if nums[i] < nums[j]:
     LIS[i] = max(LIS[i], 1 + LIS[j])
 
  return max(LIS)

Информация:

Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]