Pattern Recognition Drill
Medium Dynamic Programming
The Problem
Find the length of the longest strictly increasing subsequence.
What approach would you use?
Think about it before scrolling down.
dp[i] = length of LIS ending at i. For each j < i where a[j] < a[i]: dp[i] = max(dp[j]+1). O(n²).
Maintain a 'tails' array + bisect_left for O(n log n). More efficient but harder to implement.
Common Trap
Subsequence ≠ subarray. Elements can be non-contiguous. This changes the approach fundamentally.