Longest Increasing Subsequence

Given an integer array, return the length of the longest strictly increasing subsequence. An O(n^2) DP works but can be optimized.

Why this is worth learning

For a fixed subsequence length, only its smallest achievable ending value matters for future extensions. This dominance rule compresses quadratic endpoint DP into a sorted array of tails.

Before coding: one-minute experiment

After processing [2,6,8,3,4,5,1], what is the final tails array? Is that array itself necessarily a subsequence of the input?

Function signature

func LengthOfLIS(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: length of the LIS.

Example

nums = [10,9,2,5,3,7,101,18]
One LIS is [2,3,7,101]
Output: 4

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Patience sorting: maintain tails, where tails[i] is the smallest possible tail of any increasing subsequence of length i+1.

Invariant: tails is increasing and correctly represents minimal tails for each length.

Algorithm (step-by-step)

1. Initialize empty tails.
2. For each x in nums:
   • Find the first index i where tails[i] >= x (lower bound).
   • If none, append x; else replace tails[i] = x.
3. Return len(tails).

Correctness sketch

After a prefix, tails[k] is the smallest possible last value of any strictly increasing subsequence of length k+1 in that prefix. The tails are strictly increasing. For x, the first tail >=x identifies the longest shorter subsequence that can be extended by x; replacing that tail with x improves or preserves the best endpoint without reducing any achievable length. If no such tail exists, x extends the longest known subsequence and appends one length. Later positions cannot use x to create an even longer subsequence because their required predecessor tail is already >=x. Thus the number of tails is exactly the optimal length.

Trace (hand walkthrough)

Example input:
nums = [10,9,2,5,3,7,101,18]
One LIS is [2,3,7,101]
Output: 4

Walk:
- tails: [10] -> [9] -> [2] -> [2,5] -> [2,3] -> [2,3,7] -> [2,3,7,101] -> [2,3,7,18]
- length = 4

Pitfalls to avoid

• Treating tails as the actual subsequence (it is not).
• Using > instead of >= in lower bound (breaks strictness).

Debugging lens

Use the first tail >=x for a strictly increasing sequence; using >x incorrectly counts equal values. Test all-equal and decreasing arrays. Reconstructing the actual subsequence needs predecessor/index state beyond this length-only API.

Complexity

• Time: O(n log n).
• Extra space: O(n).

Implementation notes (Go)

• Implement binary search manually to avoid extra imports.

Reconstruction checkpoint

After processing [2,6,8,3,4,5,1], what is the final tails array? Is that array itself necessarily a subsequence of the input?

Return to 1D DP (Including Kadane) · Module quiz