Longest Increasing Subsequence in DSA Typescript - Build from Scratch

Longest Increasing Subsequence

📖 Scenario: You are analyzing a sequence of daily stock prices. You want to find the longest period during which the stock price continuously increased day by day.

🎯 Goal: Build a program that finds the length of the longest increasing subsequence in a list of stock prices.

📋 What You'll Learn

Create an array of stock prices

Use a variable to store the length of the prices array

Implement the logic to find the longest increasing subsequence length

Print the length of the longest increasing subsequence

💡 Why This Matters

🌍 Real World

Finding the longest increasing subsequence helps analyze trends in stock prices, sales data, or any sequence where growth periods matter.

💼 Career

Understanding and implementing longest increasing subsequence algorithms is useful in software development roles involving data analysis, algorithm design, and optimization.

1

Create the stock prices array

Create an array called prices with these exact values: [10, 22, 9, 33, 21, 50, 41, 60]

DSA Typescript

# Create the array 'prices' with the given values
// Your code here

Hint

Use const prices = [...] to create the array with the exact numbers.

2

Store the length of the prices array

Create a variable called n and set it to the length of the prices array using prices.length

DSA Typescript

const prices = [10, 22, 9, 33, 21, 50, 41, 60];
// Create variable 'n' to store length of 'prices'
// Your code here

Hint

Use const n = prices.length; to get the array length.

3

Implement the Longest Increasing Subsequence logic

Create an array called lis of length n filled with 1s. Then use two nested for loops: the outer loop with variable i from 1 to n - 1, and the inner loop with variable j from 0 to i - 1. Inside the inner loop, if prices[i] > prices[j] and lis[i] < lis[j] + 1, update lis[i] = lis[j] + 1. Finally, create a variable maxLis and set it to the maximum value in lis.

DSA Typescript

const prices = [10, 22, 9, 33, 21, 50, 41, 60];
const n = prices.length;
// Create array 'lis' filled with 1s
// Use nested loops with 'i' and 'j' to update 'lis'
// Calculate 'maxLis' as the maximum value in 'lis'
// Your code here

Hint

Use new Array(n).fill(1) to create lis. Use nested loops with i and j. Update lis[i] when conditions match. Use Math.max(...lis) to find the maximum.

4

Print the length of the longest increasing subsequence

Use console.log to print the value of maxLis

DSA Typescript

const prices = [10, 22, 9, 33, 21, 50, 41, 60];
const n = prices.length;
const lis = new Array(n).fill(1);
for (let i = 1; i  prices[j] && lis[i] < lis[j] + 1) {
            lis[i] = lis[j] + 1;
        }
    }
}
const maxLis = Math.max(...lis);
// Print the value of maxLis
// Your code here

Hint

Use console.log(maxLis); to print the result.