Dynamic Programming • Sequences

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence in an array using an O(N^2) dynamic programming approach.

Overview

LIS is a fundamental pattern where you build the answer for element `i` by looking backwards at all elements `j < i`.

`dp[i]` represents the length of the Longest Increasing Subsequence that STRICTLY ends at index `i`.

For a fixed `i`, scan all `j < i`. If `nums[i] > nums[j]`, then we can extend the LIS ending at `j`. `dp[i] = max(dp[i], dp[j] + 1)`.

The final answer is not necessarily `dp[n-1]`. The LIS could end anywhere, so we must return the maximum value in the entire `dp` array.

10

9

2

5

3

7

DP Array (LIS ending at i)

1

Code Tracker

:::

1let dp = Array(n).fill(1);

2for (let i = 1; i < n; i++) {

3 for (let j = 0; j < i; j++) {

4 if (nums[i] > nums[j]) {

5 dp[i] = Math.max(dp[i], dp[j] + 1);

6 }

7 }

8}

9return Math.max(...dp);