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.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The longest subsequence where each number is larger than the previous one

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with definition

   The longest subsequence where each number is larger than the previous one matches this definition exactly, others describe different or incorrect sequences.

3. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option A

4. Quick Check:

   LIS means strictly increasing subsequence [OK]

Hint: LIS means strictly increasing numbers in order [OK]

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous sequence
• Assuming equal numbers count as increasing

2. Which of the following TypeScript function signatures correctly represents a function to find the length of the Longest Increasing Subsequence in an array of numbers?

easy

A. function lengthOfLIS(nums: number): string

B. function lengthOfLIS(nums: string): number

C. function lengthOfLIS(nums: number[]): number

D. function lengthOfLIS(nums: any): void

Solution

1. Step 1: Check parameter type

   The input should be an array of numbers, so type must be number[].

2. Step 2: Check return type

   The function returns the length of LIS, which is a number.

3. Final Answer:

   function lengthOfLIS(nums: number[]): number -> Option C

4. Quick Check:

   Input array of numbers, output number length [OK]

Hint: Input is number array, output is number length [OK]

Common Mistakes:

• Using string type for input instead of number array
• Returning string instead of number
• Using void return type when output is needed

3. What is the output of the following TypeScript code?

function lengthOfLIS(nums: number[]): number {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));

medium

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Understand the DP array construction

   dp[i] stores length of LIS ending at index i. Initialize all to 1.

2. Step 2: Trace dp updates for input

   For input [10,9,2,5,3,7,101,18], dp becomes [1,1,1,2,2,3,4,4]. Max is 4.

3. Step 3: Re-check the dp array

   Actually, dp updates to [1,1,1,2,2,3,5,5] because 101 extends the subsequence ending at 7 (length 4), and 18 extends subsequence ending at 7 (length 4) as well.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   LIS length for given array is 5 [OK]

Hint: DP array max value gives LIS length [OK]

Common Mistakes:

• Confusing LIS length with subsequence elements count
• Forgetting to update dp[i] with max value
• Misreading nested loops indices

4. Identify the bug in this TypeScript function for LIS and select the fix:

function lengthOfLIS(nums: number[]): number {
  const dp = new Array(nums.length).fill(0);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

medium

A. Remove inner loop and use single loop

B. Initialize dp array with 1 instead of 0

C. Return Math.min(...dp) instead of Math.max(...dp)

D. Change loop to start i from 0 instead of 1

Solution

1. Step 1: Check dp initialization

   dp should start with 1 because each element alone is an LIS of length 1.

2. Step 2: Understand impact of zero initialization

   Starting with 0 causes dp values to be underestimated, leading to wrong max LIS length.

3. Final Answer:

   Initialize dp array with 1 instead of 0 -> Option B

4. Quick Check:

   dp starts at 1 for correct LIS length [OK]

Hint: dp array must start with 1 for each element [OK]

Common Mistakes:

• Initializing dp with 0 causing wrong results
• Changing loop start incorrectly
• Returning min instead of max

5. Given the array [3, 10, 2, 1, 20], what is the length of the Longest Increasing Subsequence if you must also return the subsequence itself? Which subsequence is correct?

hard

A. Length: 2, Subsequence: [10, 20]

B. Length: 4, Subsequence: [2, 3, 10, 20]

C. Length: 3, Subsequence: [1, 2, 20]

D. Length: 3, Subsequence: [3, 10, 20]

Solution

1. Step 1: Find LIS length and subsequence

   Possible LIS are [3,10,20] and [1,20], length 3 and 2 respectively. The longest is length 3.

2. Step 2: Verify subsequence correctness

   [3,10,20] is strictly increasing and length 3, matching the longest LIS length.

3. Final Answer:

   Length: 3, Subsequence: [3, 10, 20] -> Option D

4. Quick Check:

   LIS length 3 with subsequence [3,10,20] [OK]

Hint: Trace LIS and pick longest strictly increasing subsequence [OK]

Common Mistakes:

• Choosing subsequence with wrong order
• Confusing length with subsequence elements
• Assuming non-strictly increasing sequences