—
i
Find the length of the longest strictly increasing subsequence in an array — not necessarily contiguous. The O(n²) DP builds it element by element; the O(n log n) patience-sorttrick uses binary search on a "tails" array to solve it in near-linear time.
Given nums = [10,9,2,5,3,7,101,18], return the length of the longest strictly increasing subsequence (elements need not be contiguous). Here the answer is 4: the subsequence [2,3,7,101] (or [2,5,7,101], etc.). Note that order must be preserved — we pick indices left-to-right.
dp[i] = the length of the longest increasing subsequence that ends exactly at index i. Then dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]. Every element starts as a chain of length 1, then greedily extends the best valid predecessor. The answer is max(dp).dp[i] = 1 for every i — each element alone is a valid LIS of length 1.nums[j] < nums[i], then j can precede i; try dp[i] = max(dp[i], dp[j]+1).best = max(best, dp[i]).dp[i] represents the LIS ending at i — not the LIS of the prefix nums[0..i]. The answer is max(dp), not dp[n-1]. The last element is rarely in the longest chain.Maintain a tails array where tails[k] is the smallest tail element of all increasing subsequences of length k+1 seen so far. For each new x, binary-search for the first tails entry ≥ x. If found, replace it (keeping the tail as small as possible for future extensions). If not found, append — extending the longest chain. The length of tails at the end is the LIS length. tails is always sorted, so the binary search is valid.
[10, 9, 2, 5, 3, 7, 101, 18]. Initialize dp[i] = 1 for all i — every element is an LIS of length 1 by itself.function lengthOfLIS(nums: number[]): number {
const n = nums.length;
if (n === 0) return 0;
// dp[i] = length of LIS ending at index i
const dp: number[] = new Array(n).fill(1);
let best = 1;
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);
}
}
best = Math.max(best, dp[i]);
}
return best;
}
// ── O(n log n) patience-sorting approach ──────────────────────────────────────
// Maintain a "tails" array: tails[k] is the smallest tail of all increasing
// subsequences of length k+1. Binary search to place each element.
function lengthOfLISFast(nums: number[]): number {
const tails: number[] = []; // tails[k] = min tail of LIS length k+1
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) { // binary search for first tail >= x
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x; // extend or replace
}
return tails.length; // number of "piles" = LIS length
}1; it can always extend itself. best tracks the global maximum as we fill the table.i, scan every j < i. When nums[j] < nums[i], j is a valid predecessor; take the best: dp[i] = max(dp[i], dp[j]+1). After the inner loop, fold dp[i] into best.tails[k] stores the smallest possible tail of any increasing subsequence of length k+1. Because tails stays sorted, we binary-search for the insertion point of x (first entry ≥ x). Replacing keeps tails as small as possible — greedy choice that maximizes future extension potential. Appending grows the longest known chain by one. The array's length at the end is the LIS length.tails itself is notthe actual LIS — it's a maintenance structure. What we proved is: (1) tails is always strictly increasing (invariant), so binary search works; (2) its length equals the length of the longest IS seen. To recover the actual subsequence you need a separate parent[] array (see follow-up below).tails array costs O(log n) per element, O(n) total elements.parent[] array: when dp[i] is updated from j, set parent[i] = j. Trace back from the index where dp[idx] === best.count[] parallel to dp[]: count[i] += count[j] whenever dp[j]+1 === dp[i]. Sum count[i] where dp[i] === best.nums[j] < nums[i] to nums[j] ≤ nums[i]. In patience sort, binary-search for the first entry > x instead of ≥ x.| "longest/count subsequence (not subarray)" | DP with dp[i] = LIS ending at i |
| "strictly increasing order preserved" | nums[j] < nums[i] predecessor check |
| "O(n log n) LIS or smallest tail greedy" | patience sort with binary search on tails[] |
| "2D LIS, nested envelopes, chain of pairs" | sort + reduce to 1D LIS (patience sort) |
// O(n²) DP
const dp = new Array(nums.length).fill(1);
let best = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return best;
// O(n log n) patience sort
const tails: number[] = [];
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) { const mid = (lo+hi)>>1; if (tails[mid]<x) lo=mid+1; else hi=mid; }
tails[lo] = x;
}
return tails.length;dp[i] represent in the LIS DP?nums = [10,9,2,5,3,7,101,18], what is the LIS length?dp[i] represent in the O(n²) DP?tails entry ≥ x, you: