Longest Increasing Subseq 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Find the length of the longest strictly increasing subsequence. Elements don't need to be contiguous.

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

DP: dp[i] = length of LIS ending at index i. For each i, check all j < i where nums[j] < nums[i]. O(n²) solution.

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Find the length of the longest increasing subsequence.

dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). Initialize all dp[i] = 1. Answer = max(dp).

🧪 Test Cases

Input

lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])

Expected

4

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›