Dynamic Programming

3

[0]

10

[1]

2

[2]

1

[3]

20

[4]

dp[i] = length of LIS ending at arr[i]

1

1

1

1

1

Best LIS so far (length 1)

Press Play to fill the DP table and find the longest increasing subsequence.

LIS

Press Play to fill the dp[] array and find the Longest Increasing Subsequence.

Time

O(N^2)

Space

O(N)

Debugger · v1.0

LIVE

1function lis(arr) {

2 const n = arr.length;

3 // 1: dp[i] = LIS length ending at arr[i]

4 const dp = Array(n).fill(1);

5 // 2: Prev index for backtracking

6 const prev = Array(n).fill(-1);

7 let maxLen = 1, endIdx = 0;

9 // 3: Pick each element as LIS tail

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

11 // 4: Try all previous elements

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

13 // 5: Can arr[j] extend LIS to arr[i]?

14 if (arr[j] < arr[i]) {

15 // 6: Is this better than current dp[i]?

16 if (dp[j] + 1 > dp[i]) {

17 dp[i] = dp[j] + 1; // 7: Update

18 prev[i] = j; // 8: Track path

19 }

20 }

21 }

22 // 9: Update global best

23 if (dp[i] > maxLen) {

24 maxLen = dp[i]; endIdx = i;

25 }

26 }

28 // 10: Backtrack from endIdx

29 const lis = [];

30 let idx = endIdx;

31 // 11: Follow prev[] chain

32 while (idx !== -1) {

33 lis.unshift(arr[idx]);

34 idx = prev[idx];

35 }

36 // 12: Return LIS array

37 return lis;

38}

Debugger · v1.0

LIVE

1function lis(arr) {

2 const n = arr.length;

3 // 1: dp[i] = LIS length ending at arr[i]

4 const dp = Array(n).fill(1);

5 // 2: Prev index for backtracking

6 const prev = Array(n).fill(-1);

7 let maxLen = 1, endIdx = 0;

9 // 3: Pick each element as LIS tail

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

11 // 4: Try all previous elements

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

13 // 5: Can arr[j] extend LIS to arr[i]?

14 if (arr[j] < arr[i]) {

15 // 6: Is this better than current dp[i]?

16 if (dp[j] + 1 > dp[i]) {

17 dp[i] = dp[j] + 1; // 7: Update

18 prev[i] = j; // 8: Track path

19 }

20 }

21 }

22 // 9: Update global best

23 if (dp[i] > maxLen) {

24 maxLen = dp[i]; endIdx = i;

25 }

26 }

28 // 10: Backtrack from endIdx

29 const lis = [];

30 let idx = endIdx;

31 // 11: Follow prev[] chain

32 while (idx !== -1) {

33 lis.unshift(arr[idx]);

34 idx = prev[idx];

35 }

36 // 12: Return LIS array

37 return lis;

38}

State Inspector

No variables in scope.

Array:

Dynamic Programming

Longest Increasing Subsequence (LIS)

Step 1 of 6

Given an array of numbers, find the longest subsequence that is strictly increasing. Unlike sorting, elements must keep their original relative order. A cornerstone DP problem used in patience sorting, version history analysis, and RNA structure prediction.

The Problem

A subsequence is a selection of elements that preserves original order but can skip elements. For [3, 10, 2, 1, 20], the LIS is [3, 10, 20] (length 3) — not [3, 10, 2, 20] because 2 < 10 breaks the increasing order.

3

10

2

1

20

LIS = [3, 10, 20]