Longest Increasing Subsequence

Longest Increasing Subsequence finds the longest strictly increasing run of elements in an array, solved in O(n²) with DP or O(n log n) with a patience- sort binary-search approach.

6 min read Level 4/5 #dsa#dp#lis

What you'll learn

Write the O(n²) LIS recurrence and fill the dp array
Implement the O(n log n) patience-sort algorithm using binary search
Reconstruct the actual LIS subsequence from the DP table

The Longest Increasing Subsequence (LIS) of an array is the longest subsequence in which every element is strictly greater than the one before it. Elements need not be contiguous.

O(n²) DP Approach

State: dp[i] = length of the longest increasing subsequence ending at index i.

Recurrence: For each j less than i where nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)

Base case: dp[i] = 1 for all i (each element alone is a subsequence of length 1).

Answer: max(dp[0], dp[1], ..., dp[n-1])

function lisDP(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const dp = new Array(n).fill(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);
      }
    }
  }
  return Math.max(...dp);
}

console.log(lisDP([10, 9, 2, 5, 3, 7, 101, 18])); // 4 — [2,3,7,18] or [2,5,7,18]

Reconstructing the Subsequence

To recover the actual elements, track a parent array:

function lisWithPath(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        parent[i] = j;
      }
    }
  }

  let maxLen = 0, endIdx = 0;
  for (let i = 0; i < n; i++) {
    if (dp[i] > maxLen) { maxLen = dp[i]; endIdx = i; }
  }

  const path = [];
  for (let i = endIdx; i !== -1; i = parent[i]) path.push(nums[i]);
  return path.reverse();
}

console.log(lisWithPath([10, 9, 2, 5, 3, 7, 101, 18])); // [2, 3, 7, 18]

O(n log n) Patience Sort

The patience-sort approach maintains a list tails where tails[k] is the smallest tail element of all increasing subsequences of length k+1 seen so far. For each number, binary-search for the leftmost tail it can replace.

function lisNLogN(nums) {
  const tails = [];

  for (const num of nums) {
    let lo = 0, hi = tails.length;
    // Find leftmost position where tails[pos] >= num
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

console.log(lisNLogN([10, 9, 2, 5, 3, 7, 101, 18])); // 4

tails does not represent an actual subsequence — it’s a structural artifact of the algorithm. Its length equals the LIS length, but you need the parent approach above to recover the elements.

Complexity Comparison

Approach	Time	Space	Reconstructable?
O(n²) DP	O(n²)	O(n)	Yes (with parent array)
Patience sort	O(n log n)	O(n)	Not directly

Up Next

Edit distance generalizes sequence comparison to allow insertions, deletions, and substitutions, producing a complete metric between two strings.

Edit Distance (Levenshtein) →