Longest Increasing Subsequence Pattern

O(n²) DP: dp[i] = length of the LIS ending at i. O(n log n): maintain a "tails" array and binary search into it (patience sorting) for the optimized version.

Sub-patterns

• A — LIS O(n²). The direct DP formulation.
• B — LIS O(n log n). Patience sorting with a tails array and binary search.
• C — LIS Variants. Envelopes, 2D ordering, and other constrained versions.

Practice set (5)

• Medium — Longest Increasing Subsequence, Maximum Length of Pair Chain, Number of Longest Increasing Subsequence
• Hard — Russian Doll Envelopes, Longest Increasing Path in a Matrix