Longest Increasing Subsequence

Largest Rectangle in Histogram

Word Break

Find the length of the longest strictly increasing subsequence.

Given an integer array `nums`, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

## Example
```
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], so its length is 4.
```

**Constraints**
- `1 <= nums.length <= 2500`
- `-10^4 <= nums[i] <= 10^4`

## Follow up
Can you come up with an algorithm that runs in `O(n log n)` time?

- A subsequence keeps the original order but may skip elements.
- We want the longest run of values that strictly increase from left to right.
- We only need the **length**, not the actual subsequence.

Understanding the Problem

- Let `dp[i]` be the length of the longest increasing subsequence that ends at index `i`.
- For each `i`, look back at every `j < i`; if `nums[j] < nums[i]`, we can extend that subsequence.
- The answer is the maximum value in `dp`.

Simple O(n^2) DP

- Keep a list `sub` where `sub[k]` is the smallest possible tail of an increasing subsequence of length `k + 1`.
- For each number, binary search for the first tail `>=` it.
- Replacing that tail keeps `sub` sorted and as small as possible, leaving room to grow.

Optimizing with Patience Sorting

- `sub` is never the real subsequence, but its **length** always equals the LIS length so far.
- Using `bisect_left` enforces strictly increasing values (equal numbers overwrite rather than extend).
- That is why `[7,7,7,...]` correctly returns `1`.

Why It Works

- Time: `O(n log n)` thanks to the binary search per element.
- Space: `O(n)` for the `sub` array in the worst case.