388. In a circus tower each person must be both shorter and lighter than the person below. Given heights and weights, what is the tallest tower? (The same as Russian-doll envelopes.)
MediumDynamic programming
Technical
Show model answer
This is a 2D longest increasing subsequence. Sort by height ascending, and for equal heights sort by weight descending, so two people with the same height can never both appear in an increasing run. Then find the strict LIS on weights with the O(n log n) tails method. Total O(n log n) time and O(n) space.
The O(n²) DP over pairs (`best[i] = 1 + max(best[j])` where person j is strictly smaller in both) also works and is easier to get right first. Forgetting the descending tie-break is the classic bug: it lets equal-height people stack.