Longest increasing subsequence

Medium TimeO(n²) SpaceO(n)

A subsequence keeps the original order but may skip elements, and this one has to increase strictly at every step. Given a list, return the length of the longest such run. Its elements need not be adjacent, and an empty array answers 0.

Examples

Example 1

Input
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output
4
2, 3, 7, 18 increases and is four long; 2, 5, 7, 101 is another four.

Example 2

Input
nums = [5, 4, 3]
Output
1
Nothing increases anywhere, so the longest run is a single element.

The Code

function lengthOfLIS(nums) {
  const best = new Array(nums.length).fill(1);
  let answer = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && best[j] + 1 > best[i]) {
        best[i] = best[j] + 1;
      }
    }
    if (best[i] > answer) answer = best[i];
  }
  return answer;
}
lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]);
Done

The first 18 calls, of 44. This one does not fit on a page.

Step through lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) call by call

More like this

All dynamic programming examples (20) →