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).

Example 1:

Input: [12, 4, 14, 7, 15, 3, 16]
Output: 4
Explanation: One longest increasing subsequence is [12, 14, 15, 16] or [4, 7, 15, 16].

Example 2:

Input: [6, 2, 8, 2, 9, 3, 10, 1]
Output: 4
Explanation: The longest increasing subsequence is [6, 8, 9, 10].

Example 3:

Input: [9, 9, 9, 9, 9]
Output: 1
Explanation: Strictly increasing requires distinct values.

Constraints:

• 1 <= nums.length <= 2000
• -5000 <= nums[i] <= 5000

Solution Breakdown

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 [12, 4, 14, 7, 15, 3, 16]: dp becomes [1,1,2,2,3,1,4]; the chain 12,14,15,16 (or 4,7,15,16) reaches length 4, the maximum.

Edge cases: An empty array returns 0 via the early guard. Equal adjacent values never satisfy the strict <, so [9,9,9,9,9] 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).