Why Longest Increasing Subsequence in DSA Typescript?

The Big Idea

What if you could find the longest growing trend in your data without checking every possibility?

The Scenario

Imagine you have a list of numbers representing daily temperatures, and you want to find the longest streak where each day is warmer than the previous one.

Doing this by checking every possible combination manually is like trying to find the longest path in a maze by guessing every route.

The Problem

Manually checking all increasing sequences means looking at many combinations, which takes a very long time as the list grows.

This is slow, confusing, and easy to make mistakes because you lose track of which sequences are longest.

The Solution

The Longest Increasing Subsequence (LIS) method smartly finds the longest increasing sequence without checking every possibility.

It uses a step-by-step approach to build up solutions, saving time and avoiding errors.

Before vs After

✗ Before

function findLIS(numbers: number[]): number {
  let maxLength = 1;
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      // check sequences manually
    }
  }
  return maxLength;
}

✓ After

function findLIS(numbers: number[]): number {
  const lisLengths = Array(numbers.length).fill(1);
  for (let current = 1; current < numbers.length; current++) {
    for (let previous = 0; previous < current; previous++) {
      if (numbers[current] > numbers[previous]) {
        lisLengths[current] = Math.max(lisLengths[current], lisLengths[previous] + 1);
      }
    }
  }
  return Math.max(...lisLengths);
}

What It Enables

This concept enables you to quickly find the longest increasing pattern in data, unlocking insights in sequences like stock prices, temperatures, or scores.

Real Life Example

For example, in sports, finding the longest streak of improving scores helps coaches understand an athlete's progress over time.

Key Takeaways

Manual checking of sequences is slow and error-prone.

Longest Increasing Subsequence uses a smart stepwise method to find the answer efficiently.

This helps analyze patterns in many real-world sequences quickly.