Longest Increasing Subsequence

👶 The 5-Year-Old Summary

Find the longest chain that keeps growing! [10,9,2,5,3,7,101,18] → [2,3,7,101] or [2,5,7,101] = length 4!

🎮 Interactive Visualizer

nums = [10, 9, 2, 5, 3, 7, 101, 18]

🧠 The Brain Hack

For each element, find the longest chain ending there! dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]!

💻 The Clean Solution

def length_of_lis(nums):
    if not nums: return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# [10,9,2,5,3,7,101,18] → 4
# LIS: [2,3,7,101] or [2,3,7,18]

Time: O(n²) basic, O(n log n) optimized

Space: O(n)