The problem. Given an integer array nums, return the length of the longest strictly increasing subsequence — numbers taken left to right, not necessarily next to each other, each bigger than the one before.
![nums is 10, 9, 2, 5, 3, 7, 101, 18. dp[i] is the length of the longest increasing subsequence that ends at nums[i]: 1, 1, 1, 2, 2, 3, 4, 4. For 7, the earlier smaller numbers are 2, 5 and 3 with dp 1, 2 and 2, so dp = 2 + 1 = 3. The answer is the largest dp, 4, for example 2, 3, 7, 18.](/drawings/070bb542-4b78-4901-85df-085c039bf79c.svg)
nums = [10, 9, 2, 5, 3, 7, 101, 18] -> 4 (2, 3, 7, 18)
nums = [0, 1, 0, 3, 2, 3] -> 4 (0, 1, 2, 3)
nums = [7, 7, 7, 7] -> 1 (strictly increasing: equal values don't count)Pattern 4 is DP over sequences. With one sequence, the state is usually "the best answer that ends exactly at position i", and the transition looks back at every earlier position that could come just before it. With two sequences (LCS, Edit Distance) the state becomes a pair of prefixes and the table becomes 2D. In both, the hard part is choosing a state that makes the transition simple.
Let dp[i] be the longest increasing subsequence that ends at `nums[i]`. Whatever comes just before nums[i] in it is some nums[j] with j < i and nums[j] < nums[i] — and the part ending at j should be as long as possible. So dp[i] = 1 + max(dp[j]) over those j, or just 1 if there's none. The subsequence can end anywhere, so the answer is the largest dp[i], not dp[n - 1].
function lengthOfLIS(nums) { const best = (i, prev) => { // longest from nums[i..], all above nums[prev] if (i === nums.length) return 0; let result = best(i + 1, prev); // skip nums[i] if (prev === -1 || nums[i] > nums[prev]) result = Math.max(result, 1 + best(i + 1, i)); // take it return result; }; return best(0, -1);}Time O(2ⁿ), space O(n). Every number is taken or skipped. The state (i, prev) has only O(n²) values, so a memo would bring it to O(n²) — but the table below gets there more simply with a one-number state.
Each number looks back at every smaller number before it and extends the longest run ending there.
function lengthOfLIS(nums) { const n = nums.length; const dp = new Array(n).fill(1); // dp[i]: longest increasing subsequence ending at nums[i] for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); // put nums[i] after the one ending at j } } return Math.max(...dp); // it can end anywhere}Time O(n²), space O(n). This is the answer most interviewers expect first. To print the subsequence, also store which j gave each dp[i] and follow those links back from the largest dp.
A different state: tails[k] is the smallest number that can end an increasing subsequence of length `k + 1` among the numbers seen so far. A small tail is better — it leaves more room for what comes next. tails is always sorted, so for each new x, binary search for the first tail ≥ x: if there is none, x makes a longer subsequence; otherwise x replaces that tail, making it smaller.
function lengthOfLIS(nums) { const tails = []; // tails[k]: smallest end of an increasing run of length k + 1 for (const x of nums) { let lo = 0, hi = tails.length; // find the first tail >= x while (lo < hi) { const mid = (lo + hi) >> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; } tails[lo] = x; // append (lo === tails.length) or lower a tail } return tails.length;}Time O(n log n), space O(n). For [10, 9, 2, 5, 3, 7, 101, 18], tails goes [10] → [9] → [2] → [2, 5] → [2, 3] → [2, 3, 7] → [2, 3, 7, 101] → [2, 3, 7, 18]. Careful: tails holds the right length, but it isn't necessarily a real subsequence. Searching for the first tail ≥ x (lower bound) keeps it strictly increasing; for non-decreasing runs, search for the first tail > x instead.
[1, 3, 5, 2]: the answer is max(dp), not dp[n - 1].dp[i].nums[i] % nums[j] == 0 after sorting.