Longest Subsequence

Subsequence DP where the state at index i compares against the other elements to decide how the best run extends through it. The natural recurrence is quadratic - for each index, scan the later positions and chain onto the best compatible one - but the same problem also has an O(n log n) refinement that maintains the smallest possible tail for each subsequence length via patience sorting and binary search.

300. Longest Increasing Subsequence

Medium·

300. Longest Increasing Subsequence

---

Solutions:

FIG. 300 LONGEST INCREASING SUBSEQUENCE LRU● INTERACTIVE

Visualize

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

@lru_cache(maxsize=None)

def rec(i):

if i >= len(nums):

return 1

maxi = 1

for j in range(i, len(nums)):

if nums[i] < nums[j]:

maxi = max(maxi, 1 + rec(j))

return maxi

 

dp = [rec(i) for i in range(len(nums))]

return max(dp)

---