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·

300Longest Increasing Subsequence

4 Approaches · 2 patterns

LRU Cache

O(n^2) timeO(3n) aux

Memoization

O(n^2) timeO(2n) aux

Tabulation, O(n) Space

O(n^2) timeO(n) aux

Binary Search, O(n log n)↗ Binary Search

O(n log n) timeO(n) aux

FIG. 300 LONGEST INCREASING SUBSEQUENCE LRU● INTERACTIVE

visualization loads as you reach it

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)

---