Academy
hardJS ES5#115

LIS (longest increasing subsequence)

Prompt

Find the length of the longest strictly increasing subsequence in an array of integers. A subsequence keeps relative order but need not be contiguous. Empty array returns 0.

Solution

function lisLength(arr) {
  const dp = Array(arr.length).fill(1)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1)
    }
  }
  return Math.max(...dp, 0)
}
Mentor's take

LIS is the gateway dynamic programming problem: the answer for the whole array is built from answers to overlapping subproblems. The formulation is the part to memorize — dp[i] = length of the longest increasing subsequence that ends exactly at index i. Then for each i, look back at every j < i: if arr[j] < arr[i], the subsequence ending at j can be extended by arr[i], so dp[i] = max(dp[i], dp[j] + 1). Every element alone is a subsequence of length 1, hence the fill(1). The final answer is the max over all of dp, not dp[dp.length - 1] — the best subsequence can end anywhere.

Complexity: O(n²) time, O(n) space. The brute force — enumerate all 2^n subsequences and check each — is exponential, so the DP is already an enormous win. The known improvement is O(n log n): keep an array of "smallest tail per length" and binary-search where each element lands (patience sorting). Name it even if you don't code it; knowing the better bound exists is the senior tell.

Details that bite: "subsequence" ≠ "subarray" (no contiguity requirement — [10,9,2,5,3,7,101,18] → [2,3,7,101], length 4), "strictly increasing" means < not <= (so [7,7,7] → 1), and Math.max(...dp, 0) covers the empty array, where a bare spread of [] yields -Infinity.

Red flag: returning dp[n-1] instead of the max of dp, or confusing subsequence with contiguous subarray — each yields wrong answers on the standard test vector.

Say it: "dp[i] is the LIS ending at i; I extend any smaller predecessor and take the global max — O(n²) here, with an O(n log n) patience-sort variant using binary search on tails."