Longest increasing subsequence

Return the length of the longest strictly increasing subsequence.

Before you code

Fix the last element: dp[i] is the longest increasing subsequence ending at nums[i]. The answer is the maximum dp[i], not the last one.

Hints

1. dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), or 1.
2. O(n log n): keep tails[k], the smallest last element of an increasing subsequence of length k + 1. For each x, replace the first tail ≥ x (or append).
3. The length of tails is the answer; tails itself is not a valid subsequence.

Production & complexity notes

When solving Longest increasing subsequence on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in One-dimensional problems to reinforce the underlying pattern.

What it practices

Ending-here states and a faster refinement, from One-dimensional problems.