← Recursion & DP

Micro-Drill #157 — Longest Increasing Subsequence O(n²)

Recursion & DP Target: 15s

dp[i] = length of longest increasing subsequence ending at index i. Classic O(n²) DP.

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n  # each element is a subsequence of length 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Type it from memory. Go.

Practice Problems

• 300. Longest Increasing Subsequence
• 673. Number of Longest Increasing Subsequence

Related Coding Drills

• Drill #66 — Longest increasing subsequence Medium
• Drill #128 — Longest Common Subsequence Medium
• Drill #102 — Longest Substring Without Repeating Characters Medium