Kadane's Algorithm Maximum Subarray in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the maximum sum with the first element of the array.

DSA Rust

let mut max_so_far = [1];

Drag options to blanks, or click blank then click option'

Ai32::MIN

B0

Cnums.len()

Dnums[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing max_so_far to 0 causes incorrect results if all numbers are negative.

Using nums.len() is incorrect because it gives the length, not a value from the array.

We start max_so_far with the first element to handle arrays with all negative numbers correctly.

2fill in blank

medium

Complete the code to update the current maximum subarray sum ending at index i.

DSA Rust

current_max = std::cmp::max(nums[i], current_max [1] nums[i]);

Drag options to blanks, or click blank then click option'

A+

B*

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication changes the logic and breaks the algorithm.

Using division is not meaningful in this context.

We add nums[i] to current_max or start fresh from nums[i], whichever is larger.

3fill in blank

hard

Fix the error in updating the global maximum sum after processing each element.

DSA Rust

max_so_far = std::cmp::max(max_so_far, [1]);

Drag options to blanks, or click blank then click option'

Acurrent_max

Bnums[i]

Ci

Dmax_so_far + nums[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using nums[i] alone ignores previous sums.

Adding max_so_far and nums[i] is incorrect for max tracking.

We update max_so_far with the maximum of itself and current_max, which holds the max subarray sum ending at i.

4fill in blank

hard

Fill both blanks to complete the loop that iterates over the array starting from the second element.

DSA Rust

for i in [1]..[2] {
    // loop body
}

Drag options to blanks, or click blank then click option'

A1

B0

Cnums.len()

Dnums.len() - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 0 causes double processing of the first element.

Using nums.len() - 1 excludes the last element.

We start from index 1 and go up to nums.len() to cover all elements after the first.

5fill in blank

hard

Fill all three blanks to complete the function that returns the maximum subarray sum using Kadane's algorithm.

DSA Rust

fn max_subarray_sum(nums: Vec<i32>) -> i32 {
    let mut max_so_far = nums[0];
    let mut current_max = nums[0];
    for i in [1]..[2] {
        current_max = std::cmp::max(nums[i], current_max [3] nums[i]);
        max_so_far = std::cmp::max(max_so_far, current_max);
    }
    max_so_far
}

Drag options to blanks, or click blank then click option'

A1

Bnums.len()

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition breaks the logic.

Incorrect loop bounds cause index errors or missed elements.

Start loop from 1 to nums.len(), update current_max by adding nums[i] or starting fresh at nums[i].

Practice

1. What does Kadane's Algorithm primarily find in an array of integers?

easy

A. The maximum sum of a contiguous subarray

B. The minimum element in the array

C. The total sum of all elements

D. The maximum product of any two elements

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

2. Step 2: Differentiate from other array operations

   It does not find minimum elements, total sums, or products, but specifically the maximum sum of a continuous segment.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option A

4. Quick Check:

   Maximum subarray sum = maximum sum of contiguous elements [OK]

Hint: Kadane's finds max sum in a continuous slice [OK]

Common Mistakes:

• Confusing maximum sum with maximum product
• Thinking it finds minimum elements
• Assuming it sums all elements

2. Which of the following Rust code snippets correctly initializes variables for Kadane's Algorithm?

easy

A. let mut max_so_far = 0; let max_ending_here = i32::MIN;

B. let max_so_far = 0; let max_ending_here = 0;

C. let mut max_so_far = i32::MIN; let mut max_ending_here = 0;

D. let max_so_far = i32::MAX; let max_ending_here = 0;

Solution

1. Step 1: Identify correct initialization for Kadane's variables

   max_so_far should start at the smallest possible integer (i32::MIN) to handle all negative arrays; max_ending_here starts at 0 to accumulate sums.

2. Step 2: Check other options for correctness

   Options B and C incorrectly initialize variables, and D uses i32::MAX which is incorrect for max_so_far.

3. Final Answer:

   let mut max_so_far = i32::MIN; let mut max_ending_here = 0; -> Option C

4. Quick Check:

   Initialize max_so_far to smallest int, max_ending_here to 0 [OK]

Hint: Start max_so_far at i32::MIN, max_ending_here at 0 [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes errors with all negative arrays
• Using i32::MAX for max_so_far is wrong
• Not using mutable variables for updates

3. What is the output of the following Rust code using Kadane's Algorithm?

let nums = vec![4, -1, 2, 1, -5, 4];
let mut max_so_far = i32::MIN;
let mut max_ending_here = 0;
for &x in &nums {
    max_ending_here = (max_ending_here + x).max(x);
    max_so_far = max_so_far.max(max_ending_here);
}
println!("{}", max_so_far);

medium

A. 5

B. 7

C. 4

D. 6

Solution

1. Step 1: Trace max_ending_here and max_so_far through iterations

   Start: max_so_far = i32::MIN, max_ending_here = 0 - Add 4: max_ending_here = max(0+4,4)=4; max_so_far = max(i32::MIN,4)=4 - Add -1: max_ending_here = max(4-1,-1)=3; max_so_far = max(4,3)=4 - Add 2: max_ending_here = max(3+2,2)=5; max_so_far = max(4,5)=5 - Add 1: max_ending_here = max(5+1,1)=6; max_so_far = max(5,6)=6 - Add -5: max_ending_here = max(6-5,-5)=1; max_so_far = max(6,1)=6 - Add 4: max_ending_here = max(1+4,4)=5; max_so_far = max(6,5)=6

2. Step 2: Identify maximum subarray sum

   The maximum sum found is 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Track max_ending_here and max_so_far each step [OK]

Common Mistakes:

• Adding all positive numbers ignoring resets
• Miscomputing max_ending_here after negative values
• Choosing wrong max_so_far update

4. Identify the bug in this Rust Kadane's Algorithm implementation:

let nums = vec![-2,1,-3,4,-1,2,1,-5,4];
let mut max_so_far = 0;
let mut max_ending_here = 0;
for &x in &nums {
    max_ending_here += x;
    if max_ending_here < 0 {
        max_ending_here = 0;
    }
    if max_so_far < max_ending_here {
        max_so_far = max_ending_here;
    }
}
println!("{}", max_so_far);

medium

A. max_so_far should start at i32::MIN to handle all negative arrays

B. max_ending_here should not reset to 0 when negative

C. The loop should iterate over indices, not references

D. The println! macro is missing a newline character

Solution

1. Step 1: Analyze initialization of max_so_far

   max_so_far starts at 0, which fails if all numbers are negative because max_so_far will never update to a negative max subarray sum.

2. Step 2: Confirm correct initialization for negative arrays

   max_so_far should start at i32::MIN to correctly track maximum sums even if all are negative.

3. Final Answer:

   max_so_far should start at i32::MIN to handle all negative arrays -> Option A

4. Quick Check:

   Initialize max_so_far to smallest int for negatives [OK]

Hint: Start max_so_far at i32::MIN to handle negatives [OK]

Common Mistakes:

• Starting max_so_far at 0 causes wrong max for negative arrays
• Resetting max_ending_here incorrectly
• Ignoring reference iteration is valid in Rust

5. Given an array nums = [-2, -3, 4, -1, -2, 1, 5, -3], what is the maximum subarray sum using Kadane's Algorithm, and which subarray produces it?

hard

A. 6, subarray [4, -1, -2, 1]

B. 7, subarray [4, -1, -2, 1, 5]

C. 9, subarray [4, -1, -2, 1, 5, -3]

D. 5, subarray [1, 5]

Solution

1. Step 1: Calculate max subarray sums step-by-step

   Traverse nums: - Start max_so_far = i32::MIN, max_ending_here = 0 - -2: max_ending_here = max(0-2,-2) = -2; max_so_far = -2 - -3: max_ending_here = max(-2-3,-3) = -3; max_so_far = -2 - 4: max_ending_here = max(-3+4,4) = 4; max_so_far = 4 - -1: max_ending_here = max(4-1,-1) = 3; max_so_far = 4 - -2: max_ending_here = max(3-2,-2) = 1; max_so_far = 4 - 1: max_ending_here = max(1+1,1) = 2; max_so_far = 4 - 5: max_ending_here = max(2+5,5) = 7; max_so_far = 7 - -3: max_ending_here = max(7-3,-3) = 4; max_so_far = 7

2. Step 2: Identify subarray producing max sum

   The max sum is 7, produced by subarray [4, -1, -2, 1, 5].

3. Final Answer:

   7, subarray [4, -1, -2, 1, 5] -> Option B

4. Quick Check:

   Max sum 7 from subarray [4, -1, -2, 1, 5] [OK]

Hint: Track sums and reset start when sum drops below element [OK]

Common Mistakes:

• Including -3 in max subarray incorrectly
• Choosing shorter subarray with smaller sum
• Miscomputing max_ending_here updates