Longest Increasing Subsequence

1. Define the problem

Given an integer array nums, return the length of the longest strictly increasing subsequence . dp_i is the length of the longest increasing subsequence that ends exactly at index i. It is built from every earlier subproblem dp_j where nums_j is smaller than nums_i — take the best of them and add one . The answer is the largest value anywhere in the table.

Constraints

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [10, 9, 2, 5, 3, 7, 101, 18]

Output4

Explanation The longest increasing subsequence is [2, 3, 7, 101] (or [2, 3, 7, 18]), length 4.

2. Know the words first

In plain terms

Subsequence: A set of elements taken from an array in the same order they originally appear, even if other elements sit between them — for example, [1, 3, 4] is a subsequence of [1, 2, 3, 5, 4].

3. Visualize the solution

Build each cell from the best smaller subsequence before it

Statusbase

nums = [1, 3, 2, 4]. One cell per element, each starting at 1.

What happens in this step

nums = [1, 3, 2, 4]
dp = [1, 1, 1, 1]   (every element is a subsequence of length 1 by itself)

The cell labels are the numbers themselves; the values are the best length ending at that number. dp[0] = 1 needs no predecessor — it is already final.

Step 1 of 4

Steps to visualize

Start every dp_i at 1 — every element is an increasing subsequence of length 1 by itself.
For each index i, look at every earlier index j where nums_j < nums_i.
Set dp_i to the largest dp_j + 1 found across those earlier indices.
The answer is the maximum value anywhere in the table.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Build each cell from the best smaller subsequence before it

Statusbase

nums = [1, 3, 2, 4]. One cell per element, each starting at 1.

What happens in this step

nums = [1, 3, 2, 4]
dp = [1, 1, 1, 1]   (every element is a subsequence of length 1 by itself)

The cell labels are the numbers themselves; the values are the best length ending at that number. dp[0] = 1 needs no predecessor — it is already final.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  let best = 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;
      }
    }
    best = Math.max(best, dp[i]);
  }

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [10, 9, 2, 5, 3, 7, 101, 18]`	`4`	example from the docstring
`nums = [0, 1, 0, 3, 2, 3]`	`4`	a second worked example with repeated values
`nums = [7, 7, 7, 7, 7, 7, 7]`	`1`	every value equal, no strict increase possible
`nums = [5]`	`1`	smallest valid input, a single element
`nums = [1, 2, 3, 4, 5]`	`5`	the entire array is already increasing
`nums = [5, 4, 3, 2, 1]`	`1`	the entire array is decreasing
`nums = [1, 2]`	`2`	boundary case, two increasing elements

Longest Increasing Subsequence