Longest Increasing Subsequence

Problem

Version control systems detect the longest chain of strictly ordered commits to identify the main development thread through a branchy history. Given an integer array, return the length of the longest strictly increasing subsequence (elements do not need to be contiguous).

Input: [10, 9, 2, 5, 3, 7, 101, 18]  → 4   ([2, 3, 7, 18] or [2, 5, 7, 18])
Input: [0, 1, 0, 3, 2, 3]             → 4   ([0, 1, 2, 3])
Input: [7, 7, 7, 7]                   → 1   (strictly increasing, no two equal)

Solution

Approach: 1D DP where each cell scans all earlier cells (ending-index formulation).

Define dp[i] as the length of the longest strictly increasing subsequence that ends exactly at index i. Every element is a subsequence of length 1 by itself, so dp starts as all ones. To grow the chain ending at i, look at every earlier index j < i: if nums[j] < nums[i], then nums[i] can extend the best chain ending at j, making dp[j] + 1 a candidate for dp[i]. Taking the max over all such j gives the longest chain that lands on i. Anchoring the subsequence at its final element is the key trick - it makes the subproblems independent and orderable, since dp[i] only ever reads strictly smaller indices, all already final. The overall answer is max(dp), not dp[-1], because the longest increasing run can end anywhere, not necessarily at the last element. Trace [10, 9, 2, 5, 3, 7, 101, 18]: dp becomes [1,1,1,2,2,3,4,4]; the chain 2,3,7,18 (or 2,5,7,18) reaches length 4, the maximum.

Edge cases: An empty array returns 0 via the early guard. Equal adjacent values never satisfy the strict <, so [7,7,7,7] correctly yields 1 rather than counting duplicates.

Complexity: O(n^2) time, O(n) space - the nested scan compares every pair; a patience-sort variant with binary search reaches O(n log n).