Longest Increasing Subsequence in DSA Typescript

Mental Model

Find the longest sequence of numbers that keeps going up without breaking order. We want the biggest chain where each number is bigger than the one before.

Analogy: Imagine climbing stairs where each step is higher than the last. You want to find the longest path going up without stepping down or sideways.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
Longest Increasing Subsequence example: 10 -> 22 -> 33 -> 50 -> 60

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

LIS lengths: [1, _, _, _, _, _, _, _]

Why: Each element alone is a subsequence of length 1

Step 2: Check 22: 22 > 10, so LIS at 22 is LIS at 10 + 1 = 2

LIS lengths: [1, 2, _, _, _, _, _, _]

Why: 22 can extend the subsequence ending at 10

Step 3: Check 9: 9 is not greater than 10 or 22, so LIS at 9 is 1

LIS lengths: [1, 2, 1, _, _, _, _, _]

Why: 9 starts a new subsequence

Step 4: Check 33: 33 > 10 (LIS=1), 33 > 22 (LIS=2), 33 > 9 (LIS=1), max LIS before 33 is 2, so LIS at 33 is 3

LIS lengths: [1, 2, 1, 3, _, _, _, _]

Why: 33 extends the longest subsequence ending before it

Step 5: Check 21: 21 > 10 (LIS=1), 21 < 22, 21 > 9 (LIS=1), max LIS before 21 is 2 (from 10 or 9?), so LIS at 21 is 3

LIS lengths: [1, 2, 1, 3, 3, _, _, _]

Why: 21 extends subsequence ending at 10 or 9

Step 6: Check 50: 50 > 10 (1), 50 > 22 (2), 50 > 9 (1), 50 > 33 (3), 50 > 21 (3), max LIS before 50 is 3, so LIS at 50 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, _, _]

Why: 50 extends the longest subsequence ending before it

Step 7: Check 41: 41 > 10 (1), 41 > 22 (2), 41 > 9 (1), 41 > 33 (3), 41 > 21 (3), 41 < 50, max LIS before 41 is 3, so LIS at 41 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, 4, _]

Why: 41 extends subsequence ending at 33 or 21

Step 8: Check 60: 60 > all previous elements, max LIS before 60 is 4 (from 50 or 41), so LIS at 60 is 5

LIS lengths: [1, 2, 1, 3, 3, 4, 4, 5]

Why: 60 extends the longest subsequence ending before it

Result:

Longest Increasing Subsequence length is 5

Annotated Code

DSA Typescript

class LongestIncreasingSubsequence {
  static findLIS(arr: number[]): number {
    const n = arr.length;
    if (n === 0) return 0;
    const lis = new Array(n).fill(1);

    for (let i = 1; i < n; i++) {
      for (let j = 0; j < i; j++) {
        if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
          lis[i] = lis[j] + 1; // update LIS length at i
        }
      }
    }

    return Math.max(...lis);
  }
}

const input = [10, 22, 9, 33, 21, 50, 41, 60];
const result = LongestIncreasingSubsequence.findLIS(input);
console.log(result);

const lis = new Array(n).fill(1);

Initialize LIS lengths to 1 for each element

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

Traverse array from second element to end

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

Check all elements before i

if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {

If current element can extend LIS ending at j

lis[i] = lis[j] + 1; // update LIS length at i

Update LIS length at i to longer subsequence

return Math.max(...lis);

Return the maximum LIS length found

Output

5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements

Space: O(n) for the array that stores LIS lengths for each element

vs Alternative: This is better than checking all subsequences (which is exponential), but slower than advanced O(n log n) methods that use binary search

Edge Cases

Empty array

Returns 0 because there are no elements

DSA Typescript

if (n === 0) return 0;

All elements equal

LIS length is 1 because no element is greater than previous

DSA Typescript

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

Strictly decreasing array

LIS length is 1 because no increasing pairs

DSA Typescript

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

When to Use This Pattern

When you need to find the longest sequence of increasing numbers in order, use the Longest Increasing Subsequence pattern because it helps find the longest chain without rearranging elements.

Common Mistakes

Mistake: Updating LIS length without checking if it is longer than current value
Fix: Add condition lis[i] < lis[j] + 1 before updating to avoid overwriting longer subsequences

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you want the longest ordered chain of increasing numbers without changing order.

Remember to build LIS lengths by extending previous smaller elements and keep track of the maximum.