Find the longest subsequence whose elements are strictly increasing — elements appear in original order, values rise as you go. Unlike a subarray, gaps are allowed.

This deceptively simple problem has two classic solutions:

• O(n²) DP — clean and easy to reconstruct.
• O(n log n) — a clever binary-search optimization.

Both are worth knowing.

How It Works

O(n²) DP: define dp[i] = length of the longest increasing subsequence that ends at index i.

1. Initialize: every dp[i] = 1 — a single element is always a valid subsequence.
2. For each i: scan all j < i; if nums[j] < nums[i], extend that subsequence: dp[i] = max(dp[i], dp[j] + 1).
3. Answer: max(dp) over all indices.

O(n log n) optimization: maintain an array tails where tails[k] = the smallest possible ending value of an increasing subsequence of length k. For each element, binary-search the insertion point and overwrite — tails stays sorted, and its length is the answer.

Key Insight

The O(n²) version keeps the full history because the best subsequence ending at i may chain onto any earlier element. The tails trick compresses that history: you never need the actual subsequence for the length — only the minimal possible last value per length, which keeps tails monotonic and binary-searchable.

Worked Example

The visualizer runs on [3, 1, 8, 2, 5, 9, 4, 6, 7]:

The answer is max(dp) = 5, and the visualizer’s backtrack reveals 1, 2, 4, 6, 7. The tails array ends at [1, 2, 4, 6, 7] — length 5, matching.

Edge Cases & Pitfalls

• Strict vs non-strict — 1, 1, 1 has LIS length 1 (strict, use <) but 3 (non-decreasing, use ≤). Pick the right comparison.
• Unsorted input — the answer is at least 1 (any single element): never 0 for a non-empty array.
• Backtracking with tails — the tails array stores values, not a valid subsequence. To recover the actual sequence, keep parent pointers or stick to the O(n²) table.
• Multiple answers — many subsequences can tie for the max length.

Comparison: O(n²) DP vs O(n log n) tails

Applications

• Longest chain / nesting problems — boxes, envelopes, intervals (sort + LIS)
• Routing & scheduling — patience sorting lies at the heart of bridge-card play
• Data pipeline ordering — the minimum number of increasing subsequences to partition an array

Practice Trajectory

1. Hand-fill dp[i] for the visualizer array and confirm max(dp) = 5.
2. Trace which earlier element each dp[i] chains onto.
3. Re-derive the tails insertion for a few elements and confirm monotonicity.
4. Repeat the same problem allowing non-decreasing sequences and note the difference.
5. Implement the parent-pointer version to reconstruct the actual subsequence.