jsschools

Longest Increasing Subsequence (LIS)

Finds the length of the longest strictly increasing subsequence in an array; achieves O(n log n) with a patience-sorting style approach using binary search.

Spec ↗

Syntax

lis(arr)

Parameters

NameTypeRequiredDescription
arr number[] Yes Input array of numbers.

Returns

number — Length of the longest strictly increasing subsequence.

Examples

// O(n log n) using binary search on a tails array
function lis(arr) {
  const tails = [];
  for (const x of arr) {
    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;
}

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

// O(n²) DP with reconstruction (trades speed for simplicity)
function lisWithSequence(arr) {
  const n = arr.length;
  const dp = new Array(n).fill(1);
  const prev = new Array(n).fill(-1);
  let maxLen = 1, maxIdx = 0;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1; prev[i] = j;
      }
    }
    if (dp[i] > maxLen) { maxLen = dp[i]; maxIdx = i; }
  }

  const seq = [];
  for (let i = maxIdx; i !== -1; i = prev[i]) seq.push(arr[i]);
  return { length: maxLen, sequence: seq.reverse() };
}

console.log(lisWithSequence([3, 10, 2, 1, 20]));
Output 
{ length: 3, sequence: [ 3, 10, 20 ] }

Notes

| Case | Time | Space | |---------|------------|-------| | Best | O(n log n) | O(n) | | Average | O(n log n) | O(n) | | Worst | O(n log n) | O(n) | The O(n log n) algorithm maintains a `tails` array where `tails[i]` is the smallest tail element of any IS of length i+1 seen so far. This array is always sorted, enabling binary search. Note that `tails` is NOT the actual LIS sequence — to reconstruct the sequence, use the O(n²) DP approach with a `prev` array, or add extra bookkeeping to the fast approach. LIS is equivalent to the longest non-decreasing subsequence with a small comparator change (< vs ≤).

See also