Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original relative order but may skip elements. Strictly increasing means each chosen element is larger than the one before it, so equal values cannot both be used.

• nums holds up to a few thousand integers.
• Each value fits in a normal signed integer range, positive or negative.

Examples

• nums = [8, 6, 1, 4, 2, 9, 88, 15] → 4. One longest subsequence is 1, 4, 9, 88 (also 1, 2, 9, 15).
• nums = [2, 5, 2, 9, 4, 9] → 3, for example 2, 4, 9.
• nums = [3, 3, 3] → 1. Equal values do not count as increasing.

Hints

1. For each element, think about the longest increasing subsequence that must end exactly at that element. How does it relate to earlier elements?
2. That gives O(n^2). To go faster, ask: among all increasing subsequences of a given length, which one is the most useful to extend later?
3. Maintain, for each length L, the smallest possible tail of an increasing subsequence of length L. That list is sorted, so each new element can be placed with binary search.