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 Approachesclick to switch

1

LRU Cache

O(n^2)

O(n)

2

Memoization

O(n^2)

O(n)

3

Tabulation, O(n) Space

O(n^2)

O(n)

4

Binary Search, O(n log n)

O(n log n)

O(n)

Explanation

Define rec(i) as the length of the longest increasing subsequence that starts at index i. From i, try every later index j > i with nums[j] > nums[i] and extend by 1 + rec(j), keeping the best. @lru_cache memoizes each rec(i) so overlapping calls are computed once, and the answer is the max over all starting indices.

Analysis

Time

O(n^2)

• There are n distinct subproblems rec(i), and each scans the up to n indices after it, giving n * n work.

Space

O(n)

• The lru cache stores one entry per index, and the recursion depth can reach n.

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)

---