Longest Increasing Subsequence

01 · Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

02 · Analysis

The main solution defines dp[i] as the longest strictly increasing subsequence ending at i, then extends every earlier smaller value. The best can end anywhere, so return max(dp), or 0 for empty input. Time O(n^2), space O(n). The alternative keeps the smallest possible tail for each length: replace the first tail >= x, or append if none exists. Smaller tails preserve at least as many future extensions; duplicates replace rather than lengthen. Binary search yields O(n log(n+1)) time and O(n) space. Tails themselves need not form one actual subsequence.

03 · Solution

Reference solution

1. DP by ending index: O(n²)

1def lengthOfLIS(nums: List[int]) -> int:
2    n = len(nums)
3    dp = [1] * n
4
5    for i in range(n):
6        for j in range(i):
7            if nums[j] < nums[i]:
8                dp[i] = max(dp[i], dp[j] + 1)
9
10    return max(dp, default=0)

2. Minimum tails with binary search: O(n log n)

1from bisect import bisect_left
2
3def lengthOfLIS(nums: List[int]) -> int:
4    tails = []
5    for value in nums:
6        position = bisect_left(tails, value)
7        if position == len(tails):
8            tails.append(value)
9        else:
10            tails[position] = value
11    return len(tails)

Coin Change

Maximum-sum Grid Path