Longest Increasing Subsequence in DSA Rust - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize dp array with 1s

↓

For each element i

↓

Check all elements j < i

↓

If arr[j

↓

Update dp[i

↓

Repeat for all i

↓

Find max value in dp

↓

Longest Increasing Subsequence length found

We start with the array, create a dp array to store LIS lengths ending at each index, update dp by checking previous smaller elements, then find the maximum dp value as the LIS length.

Execution Sample

DSA Rust

let arr = [10, 9, 2, 5, 3, 7, 101, 18];
let mut dp = vec![1; arr.len()];
for i in 1..arr.len() {
    for j in 0..i {
        if arr[j] < arr[i] {
            dp[i] = dp[i].max(dp[j] + 1);
        }
    }
}
let lis = *dp.iter().max().unwrap();
println!("{}", lis);

This code calculates the length of the longest increasing subsequence in the array.

Execution Table

Step	Operation	Index i	Index j	Condition arr[j]<arr[i]	dp Array State	Action Taken
1	Initialize dp	-	-	-	[1, 1, 1, 1, 1, 1, 1, 1]	Set all dp values to 1
2	i=1, j=0	1	0	arr[0]=10 < arr[1]=9? No	[1, 1, 1, 1, 1, 1, 1, 1]	No update
3	i=2, j=0	2	0	arr[0]=10 < arr[2]=2? No	[1, 1, 1, 1, 1, 1, 1, 1]	No update
4	i=2, j=1	2	1	arr[1]=9 < arr[2]=2? No	[1, 1, 1, 1, 1, 1, 1, 1]	No update
5	i=3, j=0	3	0	arr[0]=10 < arr[3]=5? No	[1, 1, 1, 1, 1, 1, 1, 1]	No update
6	i=3, j=1	3	1	arr[1]=9 < arr[3]=5? No	[1, 1, 1, 1, 1, 1, 1, 1]	No update
7	i=3, j=2	3	2	arr[2]=2 < arr[3]=5? Yes	[1, 1, 1, 2, 1, 1, 1, 1]	dp[3] = max(1, dp[2]+1)=2
8	i=4, j=0	4	0	arr[0]=10 < arr[4]=3? No	[1, 1, 1, 2, 1, 1, 1, 1]	No update
9	i=4, j=1	4	1	arr[1]=9 < arr[4]=3? No	[1, 1, 1, 2, 1, 1, 1, 1]	No update
10	i=4, j=2	4	2	arr[2]=2 < arr[4]=3? Yes	[1, 1, 1, 2, 2, 1, 1, 1]	dp[4] = max(1, dp[2]+1)=2
11	i=4, j=3	4	3	arr[3]=5 < arr[4]=3? No	[1, 1, 1, 2, 2, 1, 1, 1]	No update
12	i=5, j=0	5	0	arr[0]=10 < arr[5]=7? No	[1, 1, 1, 2, 2, 1, 1, 1]	No update
13	i=5, j=1	5	1	arr[1]=9 < arr[5]=7? No	[1, 1, 1, 2, 2, 1, 1, 1]	No update
14	i=5, j=2	5	2	arr[2]=2 < arr[5]=7? Yes	[1, 1, 1, 2, 2, 2, 1, 1]	dp[5] = max(1, dp[2]+1)=2
15	i=5, j=3	5	3	arr[3]=5 < arr[5]=7? Yes	[1, 1, 1, 2, 2, 3, 1, 1]	dp[5] = max(2, dp[3]+1)=3
16	i=5, j=4	5	4	arr[4]=3 < arr[5]=7? Yes	[1, 1, 1, 2, 2, 3, 1, 1]	dp[5] = max(3, dp[4]+1)=3
17	i=6, j=0	6	0	arr[0]=10 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 2, 1]	dp[6] = max(1, dp[0]+1)=2
18	i=6, j=1	6	1	arr[1]=9 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 2, 1]	dp[6] = max(2, dp[1]+1)=2
19	i=6, j=2	6	2	arr[2]=2 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 2, 1]	dp[6] = max(2, dp[2]+1)=2
20	i=6, j=3	6	3	arr[3]=5 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 3, 1]	dp[6] = max(2, dp[3]+1)=3
21	i=6, j=4	6	4	arr[4]=3 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 3, 1]	dp[6] = max(3, dp[4]+1)=3
22	i=6, j=5	6	5	arr[5]=7 < arr[6]=101? Yes	[1, 1, 1, 2, 2, 3, 4, 1]	dp[6] = max(3, dp[5]+1)=4
23	i=7, j=0	7	0	arr[0]=10 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 2]	dp[7] = max(1, dp[0]+1)=2
24	i=7, j=1	7	1	arr[1]=9 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 2]	dp[7] = max(2, dp[1]+1)=2
25	i=7, j=2	7	2	arr[2]=2 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 2]	dp[7] = max(2, dp[2]+1)=2
26	i=7, j=3	7	3	arr[3]=5 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 3]	dp[7] = max(2, dp[3]+1)=3
27	i=7, j=4	7	4	arr[4]=3 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 3]	dp[7] = max(3, dp[4]+1)=3
28	i=7, j=5	7	5	arr[5]=7 < arr[7]=18? Yes	[1, 1, 1, 2, 2, 3, 4, 4]	dp[7] = max(3, dp[5]+1)=4
29	i=7, j=6	7	6	arr[6]=101 < arr[7]=18? No	[1, 1, 1, 2, 2, 3, 4, 4]	No update
30	Find max in dp	-	-	-	[1, 1, 1, 2, 2, 3, 4, 4]	Max dp value is 4
31	End	-	-	-	[1, 1, 1, 2, 2, 3, 4, 4]	LIS length = 4

💡 All elements processed, dp array fully updated, maximum dp value found as LIS length

Variable Tracker

Variable	Start	After Step 7	After Step 11	After Step 16	After Step 22	After Step 29	Final
dp	[1,1,1,1,1,1,1,1]	[1,1,1,2,1,1,1,1]	[1,1,1,2,2,1,1,1]	[1,1,1,2,2,3,1,1]	[1,1,1,2,2,3,4,1]	[1,1,1,2,2,3,4,4]	[1,1,1,2,2,3,4,4]
i	0	3	4	5	6	7	End
j	-	2	4	5	6	6	-

Key Moments - 3 Insights

Why do we initialize all dp values to 1 at the start?

Each element alone is an increasing subsequence of length 1, so dp starts with 1 for all indices (see Step 1 in execution_table).

Why do we only update dp[i] when arr[j] < arr[i]?

Because the subsequence must be strictly increasing, so only previous smaller elements can extend the subsequence (see Steps 7, 10, 15).

How do we find the final longest increasing subsequence length?

After filling dp, the maximum value in dp is the length of the longest increasing subsequence (see Step 30).

Visual Quiz - 3 Questions

Look at the execution_table at Step 7. What is the dp array state after this step?

A [1, 1, 1, 1, 1, 1, 1, 1]

B [1, 1, 1, 2, 1, 1, 1, 1]

C [1, 2, 1, 2, 1, 1, 1, 1]

D [1, 1, 2, 2, 1, 1, 1, 1]

💡 Hint

Check the dp Array State column at Step 7 in execution_table.

At which iteration i does dp[6] first update to 4?

A Step 22

B Step 18

C Step 20

D Step 16

💡 Hint

Look at the Action Taken column for dp[6] updates in execution_table.

If the array was strictly decreasing, what would be the final dp array?

A Increasing sequence from 1 to n

B All zeros

C All 1s

D Random values

💡 Hint

Refer to variable_tracker and key_moments about dp initialization and updates.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Use dp array where dp[i] = length of LIS ending at i
- Initialize dp with 1s (each element alone)
- For each i, check all j < i: if arr[j] < arr[i], dp[i] = max(dp[i], dp[j]+1)
- Result is max value in dp
- Time complexity: O(n^2)

Full Transcript

Longest Increasing Subsequence finds the longest strictly increasing sequence inside an array. We create a dp array where each position starts at 1, meaning the smallest subsequence is the element itself. We then check for each element all previous elements smaller than it and update dp[i] to the longest subsequence length found plus one. After processing all elements, the maximum value in dp is the length of the longest increasing subsequence. This method uses nested loops and runs in quadratic time.

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