Longest Increasing Subsequence

Examples

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

One such subsequence is [2, 3, 7, 101]; another is [2, 3, 7, 18].

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

[0, 1, 2, 3] is a valid increasing subsequence of length 4.

Input: nums = [7, 7, 7, 7]
Output: 1

Since it must be strictly increasing, repeats can't extend a subsequence past length 1.

Constraints

• 1 <= nums.length <= 2500

• -10^4 <= nums[i] <= 10^4

Approach

For every index i, ask: if the subsequence has to end exactly at nums[i], how long can it be? That's 1 (just nums[i] by itself) plus the best of all the "ends here" answers for earlier, smaller numbers that could feed into it. Computing that for every index and taking the overall best gives the answer, but comparing every index against every earlier index costs O(n^2).

There's a faster way that avoids ever needing to know which specific number extends which subsequence. Keep a running list, "tails," where tails[k] is the smallest possible last value of any increasing subsequence of length k + 1 seen so far. For each new number, find the first spot in "tails" it can replace (the first tail value that's not smaller than it) using binary search, since "tails" stays sorted — either it extends the list (a new longest length found) or it replaces an entry with a smaller, more promising tail value for that length. The final length of "tails" is the answer.

Solutions

Brute Force — Plain Recursion

For every starting index, recursively try including or skipping each later number (only including ones that keep the sequence increasing), and take the longest result found.

function lengthOfLIS(nums) {
  function longestFrom(i, prevValue) {
    let best = 0;
    for (let j = i; j < nums.length; j++) {
      if (nums[j] > prevValue) {
        best = Math.max(best, 1 + longestFrom(j + 1, nums[j]));
      }
    }
    return best;
  }

  return longestFrom(0, -Infinity);
}

Time: O(2^n) · Space: O(n) — recursion depth

Better — Bottom-Up DP

For each index, compute the longest increasing subsequence ending exactly there, by checking every earlier index with a smaller value.

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1); // every number alone is a subsequence of length 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;
}

Time: O(n^2) · Space: O(n)

Optimal — Binary Search on Tails

Maintain the smallest possible tail value for an increasing subsequence of each length seen so far, and use binary search to find where each new number fits in — either extending the longest subsequence found, or improving a shorter one's tail.

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

  for (const num of nums) {
    let low = 0;
    let high = tails.length;

    // Binary search for the first tail value >= num
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (tails[mid] < num) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    if (low === tails.length) {
      tails.push(num); // num extends the longest subsequence found so far
    } else {
      tails[low] = num; // num gives a smaller, more promising tail for this length
    }
  }

  return tails.length;
}

Time: O(n log n) · Space: O(n)