Why Longest Increasing Subsequence in DSA Rust?

The Big Idea

Discover how to find the longest rising pattern in a sea of numbers without getting lost in endless guesses!

The Scenario

Imagine you have a list of numbers representing daily temperatures, and you want to find the longest period where the temperature keeps rising each day.

Doing this by checking every possible sequence 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 every combination, which grows very fast and becomes impossible for long lists.

This takes too much time and is easy to make mistakes, especially when the list is large.

The Solution

The Longest Increasing Subsequence (LIS) method smartly finds the longest rising sequence without checking all possibilities.

It uses a clever way to remember the best sequences found so far, making the search fast and reliable.

Before vs After

✗ Before

fn longest_increasing_subsequence(nums: &[i32]) -> usize {
    let mut max_length = 1;
    for i in 0..nums.len() {
        for j in i+1..nums.len() {
            if nums[j] > nums[i] {
                // check sequences manually
            }
        }
    }
    max_length
}

✓ After

fn longest_increasing_subsequence(nums: &[i32]) -> usize {
    let mut lis = vec![];
    for &num in nums {
        match lis.binary_search(&num) {
            Ok(pos) | Err(pos) => {
                if pos == lis.len() {
                    lis.push(num);
                } else {
                    lis[pos] = num;
                }
            }
        }
    }
    lis.len()
}

What It Enables

This lets you quickly find the longest rising pattern in data, unlocking insights in time series, stock prices, or any ordered information.

Real Life Example

In stock market analysis, LIS helps find the longest period where stock prices keep increasing, guiding investment decisions.

Key Takeaways

Manual checking is slow and error-prone for long sequences.

LIS uses smart searching and updating to find the longest increasing sequence efficiently.

This method makes analyzing trends in data fast and practical.

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