Longest Increasing Subsequence

Solution

Let $n$ be the length of the array.

The brute force $O(n^3)$ solution is omitted.

Follow Up

Could you come up with the $O(n^2)$ solution?

DFS Recursion w/ Memo

$dfs(i)$ 表示以 nums[i] 结尾的最长递增子序列（LIS）的长度。

$\text{dfs}(i) = \max{(\text{dfs}(j))} + 1 \text{\quad for } j < i \text{ and } \text{nums}[j] < \text{nums}[i]$

def lengthOfLIS(self, nums: List[int]) -> int:
    # dfs(i): 以 nums[i] 结尾的LIS
    @cache
    def dfs(i):
        res = 0
        for j in range(i):
            if nums[j] < nums[i]:
                res = max(res, dfs(j))
        return res + 1 # 1 means num[i]
    
    n = len(nums)
    return max(dfs(i) for i in range(n))

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> memo(n);
    auto dfs = [&](this auto&& dfs, int i) -> int {
        int& res = memo[i]; // reference here
        if (res > 0) { // having calculated
            return res;
        }
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                res = max(res, dfs(j));
            }
        }
        return ++res;
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));
    }
    return ans;
}

DP

Complexity

time: $O(n^2)$
space: $O(n)$

def lengthOfLIS(self, nums: List[int]) -> int:
    # 以 nums[i] 结尾的LIS
    n = len(nums)
    dp = [0 for _ in range(n)]
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j])
        dp[i] += 1
    return max(dp)

Could you improve it to $O(n \log n)$ time complexity?

Greedy Algorithm & Binary Search

g[i] 表示长为 i+1 的上升子序列的末尾元素的最小值。

Complexity

time: $O(n \log n)$
space: $O(n)$

def lengthOfLIS(self, nums: List[int]) -> int:
    g = []
    for x in nums:
        j = bisect_left(g, x)
        if j == len(g):
            g.append(x)
        else:
            g[j] = x
    return len(g)