LIS & LCS

The Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) are two of the most studied sequence DP problems. They appear directly in interviews and as building blocks for harder problems (edit distance, diff algorithms, sequence alignment).

Longest Increasing Subsequence — O(n²) DP

Given an array, find the length of the longest subsequence of strictly increasing elements. A subsequence preserves relative order but need not be contiguous.

State: dp[i] = length of the LIS ending at index i Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i] Base case: dp[i] = 1 for all i (every single element is a subsequence of length 1) Answer: max(dp[i]) over all i

// LIS — O(n²) time, O(n) space
function lisDP(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);  // base: each element alone = length 1

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {          // strictly increasing
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

// Trace for [10, 9, 2, 5, 3, 7, 101, 18]:
// dp[0]=1 (10)
// dp[1]=1 (9, no j<1 with nums[j]<9 ... wait, dp[1]: j=0, nums[0]=10 > 9, skip → dp[1]=1)
// dp[2]=1 (2, no smaller before it)
// dp[3]=2 (5, nums[2]=2 < 5 → dp[3] = dp[2]+1 = 2)
// dp[4]=2 (3, nums[2]=2 < 3 → dp[4] = 2)
// dp[5]=3 (7, 2<7, 5<7, 3<7 → max(dp[2],dp[3],dp[4])+1 = 3)
// dp[6]=4 (101 is greater than all → dp[5]+1=4)
// dp[7]=4 (18, greater than 2,5,3,7 → dp[5]+1=4)
// answer = max(dp) = 4

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

LIS — O(n log n) Patience Sorting

The O(n²) approach is fine for n ≤ 2000 but too slow for n ≤ 100,000. The patience sorting algorithm achieves O(n log n) by maintaining a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1 seen so far.

Key property: tails is always sorted in ascending order. When we process each element x:

If x is larger than all tails, append it (extends the LIS by 1)
Otherwise, use binary search to find the leftmost tail ≥ x and replace it with x (this doesn't change the LIS length yet, but makes future extensions easier)

// LIS — O(n log n) patience sorting
function lisOptimal(nums) {
  const tails = [];  // tails[i] = smallest tail of IS of length i+1

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

    tails[lo] = num;  // place or replace
  }

  return tails.length;  // length of tails = LIS length
}

// Trace for [10, 9, 2, 5, 3, 7, 101, 18]:
// num=10: tails=[], lo=0 → tails=[10]
// num=9:  lo=0 (tails[0]=10≥9) → tails=[9]
// num=2:  lo=0 → tails=[2]
// num=5:  lo=1 (tails[0]=2<5, hi=1) → tails=[2,5]
// num=3:  lo=1 (tails[0]=2<3, tails[1]=5≥3) → tails=[2,3]
// num=7:  lo=2 → tails=[2,3,7]
// num=101: lo=3 → tails=[2,3,7,101]
// num=18: lo=3 (7<18, 101≥18) → tails=[2,3,7,18]
// answer = tails.length = 4 ✓

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

Note

The tails array does NOT represent the actual LIS — only its length. After the algorithm, tails[3] might be 18 (not 101) even though 101 appeared in a valid LIS. To reconstruct the actual sequence, use the parent pointer method below.

Reconstructing the Actual LIS

To recover the actual subsequence (not just its length), track parent pointers during the O(n²) DP, then backtrack from the optimal ending index.

// Reconstruct LIS — O(n²) with backtracking
function lisReconstruct(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;  // track where we came from
      }
    }
  }

  // Find the index of the maximum value in dp
  let maxLen = 0, endIdx = 0;
  for (let i = 0; i < n; i++) {
    if (dp[i] > maxLen) { maxLen = dp[i]; endIdx = i; }
  }

  // Backtrack to reconstruct the sequence
  const lis = [];
  let cur = endIdx;
  while (cur !== -1) {
    lis.push(nums[cur]);
    cur = parent[cur];
  }

  return lis.reverse();
}

console.log(lisReconstruct([10, 9, 2, 5, 3, 7, 101, 18]));
// [2, 3, 7, 18] or [2, 3, 7, 101] (both valid length-4 LIS)

Longest Common Subsequence — 2D DP

Given two strings, find the length of their longest common subsequence (LCS). A common subsequence appears in both strings in the same relative order, but not necessarily contiguously.

State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1] Recurrence:

If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (extend LCS)
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one char from either string) Base cases: dp[i][0] = 0 and dp[0][j] = 0 (empty string has LCS 0)

// LCS Length — O(m·n) time, O(m·n) space
function lcsLength(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;        // characters match
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // take best
      }
    }
  }

  return dp[m][n];
}

// Table trace for text1="abcde", text2="ace":
//     ""  a  c  e
// ""   0  0  0  0
// a    0  1  1  1
// b    0  1  1  1
// c    0  1  2  2
// d    0  1  2  2
// e    0  1  2  3   ← answer

console.log(lcsLength('abcde', 'ace'));    // 3
console.log(lcsLength('abc',   'abc'));    // 3
console.log(lcsLength('abc',   'def'));    // 0

Reconstructing the LCS String

To recover the actual LCS (not just its length), backtrack through the DP table:

If text1[i-1] == text2[j-1]: include this character, move diagonally
Else: move in the direction of the larger neighbor

// Print the LCS string — O(m·n) time, O(m·n) space
function lcsPrint(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  // Backtrack to reconstruct
  let i = m, j = n;
  const result = [];
  while (i > 0 && j > 0) {
    if (text1[i - 1] === text2[j - 1]) {
      result.push(text1[i - 1]);  // this char is in the LCS
      i--; j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return result.reverse().join('');
}

console.log(lcsPrint('abcde', 'ace'));     // 'ace'
console.log(lcsPrint('AGGTAB', 'GXTXAYB')); // 'GTAB'

LCS vs Longest Common Substring

These two problems are frequently confused. The key difference:

LCS (Subsequence): characters can be non-contiguous. "ace" is a subsequence of "abcde"
LCS (Substring): characters must be contiguous. "abc" is a substring of "abcde" but "ace" is not

The DP recurrence differs in one critical line:

// Longest Common Substring — O(m·n) time
function longestCommonSubstring(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  let maxLen = 0;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
      // KEY DIFFERENCE: if chars don't match, dp[i][j] stays 0
      // (can't extend a substring across a mismatch)
    }
  }

  return maxLen;
}

console.log(longestCommonSubstring('abcde', 'cdeab'));  // 3 ('cde')
console.log(lcsLength('abcde', 'cdeab'));               // 4 ('cdea' — but 'abcde' vs 'cdeab': 'cdea' is subseq? No: 'abde' or 'cdea'... 'abcde'↔'cdeab': 'cdea' needs c,d,e in text1 and a,b in text2... Let's trust the function)

Property	LCS (Subsequence)	LCS (Substring)
Contiguous?	No	Yes
Mismatch handling	max(dp[i-1][j], dp[i][j-1])	dp[i][j] = 0
Answer location	dp[m][n]	max seen during fill
Example	"ace" in "abcde"	"abc" in "abcde"

Complexity Summary

Algorithm	Time	Space	Notes
LIS — O(n²) DP	O(n²)	O(n)	Simple, can reconstruct easily
LIS — patience sort	O(n log n)	O(n)	Optimal; tails array trick
LCS length	O(m·n)	O(m·n)	Can reduce to O(n) with rolling array
LCS print	O(m·n)	O(m·n)	Need full table for backtracking
LCS substring	O(m·n)	O(m·n)	Same table, different update rule

Tip

LIS reduces to LCS: the LIS of array A equals the LCS of A and sorted(unique(A)). This shows the two problems are closely related. The patience sort approach is faster for LIS specifically because binary search exploits the sorted tails structure.

LIS dp[i] = length of longest increasing subsequence ending at i
LCS dp[i][j] = LCS of first i chars of text1 and first j chars of text2
Both use parent pointers / backtracking to reconstruct the actual sequence
LCS substring differs: no propagation across mismatches, track running max
Patience sort achieves O(n log n) for LIS using binary search on tails array