Longest Increasing Subsequence in DSA Rust - Build from Scratch

Longest Increasing Subsequence

📖 Scenario: Imagine you are analyzing a sequence of daily temperatures to find the longest period where the temperature keeps rising day by day.

🎯 Goal: You will write a Rust program to find the length of the longest increasing subsequence in a list of numbers.

📋 What You'll Learn

Create a vector called numbers with the exact values [10, 22, 9, 33, 21, 50, 41, 60]

Create a vector called lis to store the length of the longest increasing subsequence ending at each index

Use a nested for loop with variables i and j to compute the lis values

Print the maximum value from the lis vector

💡 Why This Matters

🌍 Real World

Finding the longest increasing subsequence helps in analyzing trends like stock prices, temperatures, or any data that changes over time.

💼 Career

Understanding dynamic programming and sequence analysis is useful for software engineers working on data analysis, finance, and algorithm design.

1

Create the initial vector of numbers

Create a vector called numbers with the exact values [10, 22, 9, 33, 21, 50, 41, 60].

DSA Rust

# Create the vector numbers with the given values
# Your code here

Hint

Use let numbers = vec![10, 22, 9, 33, 21, 50, 41, 60]; to create the vector.

2

Initialize the LIS vector

Create a mutable vector called lis with the same length as numbers, where each element is initialized to 1.

DSA Rust

fn main() {
    let numbers = vec![10, 22, 9, 33, 21, 50, 41, 60];
    // Initialize lis vector with 1s
    // Your code here
}

Hint

Use vec![1; numbers.len()] to create a vector filled with 1s.

3

Compute the LIS values using nested loops

Use a nested for loop with variables i and j where i goes from 1 to numbers.len() and j goes from 0 to i. Inside the inner loop, if numbers[i] > numbers[j] and lis[i] < lis[j] + 1, update lis[i] to lis[j] + 1.

DSA Rust

fn main() {
    let numbers = vec![10, 22, 9, 33, 21, 50, 41, 60];
    let mut lis = vec![1; numbers.len()];
    // Compute LIS values
    // Your code here
}

Hint

Use two loops: outer loop from 1 to length, inner loop from 0 to i. Update lis[i] when conditions meet.

4

Print the length of the longest increasing subsequence

Print the maximum value from the lis vector using println!.

DSA Rust

fn main() {
    let numbers = vec![10, 22, 9, 33, 21, 50, 41, 60];
    let mut lis = vec![1; numbers.len()];
    for i in 1..numbers.len() {
        for j in 0..i {
            if numbers[i] > numbers[j] && lis[i] < lis[j] + 1 {
                lis[i] = lis[j] + 1;
            }
        }
    }
    // Print the maximum value in lis
    // Your code here
}

Hint

Use lis.iter().max().unwrap() to find the maximum value and print it.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given list of numbers?

easy

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

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

C. The longest sequence of equal numbers

D. The shortest sequence containing all numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is the longest part of the list where every next number is bigger than the one before.

2. Step 2: Compare options with definition

   The longest sequence where each number is larger than the previous one matches the definition exactly. Other options describe different sequences.

3. Final Answer:

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

4. Quick Check:

   LIS = longest increasing sequence [OK]

Hint: LIS means strictly increasing sequence length [OK]

Common Mistakes:

• Confusing increasing with decreasing sequences
• Thinking LIS means equal numbers
• Mixing LIS with shortest sequences

2. Which Rust code snippet correctly initializes a vector to store LIS lengths for each element in a list named nums?

easy

A. let mut lis = vec![0; nums.len()];

B. let mut lis = vec![1; nums.len()];

C. let lis = vec![0; nums.len()];

D. let lis = vec![1; nums.len()];

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because the smallest subsequence includes the element itself.

2. Step 2: Check Rust syntax for mutable vector

   We need a mutable vector to update LIS values, so mut is required. The vector should be initialized with 1s.

3. Final Answer:

   let mut lis = vec![1; nums.len()]; -> Option B

4. Quick Check:

   Mutable vector with 1s = let mut lis = vec![1; nums.len()]; [OK]

Hint: LIS lengths start at 1, vector must be mutable [OK]

Common Mistakes:

• Initializing with zeros instead of ones
• Forgetting mut keyword for updates
• Using immutable vector when updates needed

3. What is the output of the following Rust code that calculates the length of the LIS for nums = vec![10, 9, 2, 5, 3, 7, 101, 18]?

fn length_of_lis(nums: Vec<i32>) -> usize {
    let n = nums.len();
    let mut lis = vec![1; n];
    for i in 1..n {
        for j in 0..i {
            if nums[i] > nums[j] {
                lis[i] = lis[i].max(lis[j] + 1);
            }
        }
    }
    *lis.iter().max().unwrap()
}

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    println!("{}", length_of_lis(nums));
}

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace LIS calculation for each element

   Starting with lis = [1,1,1,1,1,1,1,1]. - i=1: nums[1]=9 < 10, no update - i=2: nums[2]=2 < previous, no update - i=3: nums[3]=5 > 2, lis[3]=max(1, lis[2]+1)=2 - i=4: nums[4]=3 > 2, lis[4]=2 - i=5: nums[5]=7 > 5 and 3, lis[5]=max(1, lis[3]+1=3, lis[4]+1=3)=3 - i=6: nums[6]=101 > all previous, lis[6]=max(1, lis[5]+1=4, others less)=4 - i=7: nums[7]=18 > 7, lis[7]=max(1, lis[5]+1=4)=4

2. Step 2: Find maximum LIS value

   The maximum value in lis is 4, which is the length of the longest increasing subsequence.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   LIS length = 4 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing sequences
• Forgetting to update lis[i] with max value
• Misreading the nested loops

4. Identify the bug in this Rust function that attempts to compute the LIS length:

fn length_of_lis(nums: Vec<i32>) -> usize {
    let n = nums.len();
    let mut lis = vec![1; n];
    for i in 0..n {
        for j in 0..i {
            if nums[i] < nums[j] {
                lis[i] = lis[i].max(lis[j] + 1);
            }
        }
    }
    *lis.iter().max().unwrap()
}

What is the error?

medium

A. The function should return the sum of lis instead of max

B. The vector lis should be initialized with zeros instead of ones

C. The outer loop should start from 1 instead of 0

D. The comparison should be nums[i] > nums[j] instead of nums[i] < nums[j]

Solution

1. Step 1: Analyze the comparison condition

   The LIS requires increasing order, so we must check if nums[i] > nums[j]. The code incorrectly uses nums[i] < nums[j], which finds decreasing sequences.

2. Step 2: Confirm other parts are correct

   Initialization with ones and returning max are correct. Starting outer loop at 0 is valid but less efficient.

3. Final Answer:

   The comparison should be nums[i] > nums[j] instead of nums[i] < nums[j] -> Option D

4. Quick Check:

   Correct comparison is > for LIS [OK]

Hint: Check comparison signs for increasing sequences [OK]

Common Mistakes:

• Using less than instead of greater than
• Initializing lis with zeros
• Returning sum instead of max

5. Given a list nums = vec![3, 10, 2, 1, 20], how would you modify the LIS algorithm to also return the actual longest increasing subsequence, not just its length?

hard

A. Sort the list first, then find LIS length on sorted list

B. Use a stack to push elements and pop when sequence breaks

C. Keep a predecessor array to track previous indices and reconstruct the sequence after computing LIS lengths

D. Return the maximum value in nums as the LIS length and sequence

Solution

1. Step 1: Understand LIS length vs sequence

   Length calculation only tracks counts. To get the sequence, we must remember which elements lead to current LIS values.

2. Step 2: Use predecessor array for reconstruction

   Maintain an array storing the index of the previous element in the LIS for each position. After LIS lengths are computed, backtrack from the max index to build the sequence.

3. Step 3: Reject incorrect options

   Sorting changes order, invalid for LIS. Stack method is not standard for LIS. Returning max value is incorrect.

4. Final Answer:

   Keep a predecessor array to track previous indices and reconstruct the sequence after computing LIS lengths -> Option C

5. Quick Check:

   Predecessor array enables LIS reconstruction [OK]

Hint: Track previous indices to rebuild LIS sequence [OK]

Common Mistakes:

• Sorting input before LIS calculation
• Confusing stack usage with LIS logic
• Returning max element instead of sequence