Kadane's Algorithm Maximum Subarray in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of Kadane's algorithm on this array?

Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], what is the maximum subarray sum found by Kadane's algorithm?

DSA Rust

fn max_subarray_sum(nums: &[i32]) -> i32 {
    let mut max_ending_here = 0;
    let mut max_so_far = i32::MIN;
    for &x in nums {
        max_ending_here = (max_ending_here + x).max(x);
        max_so_far = max_so_far.max(max_ending_here);
    }
    max_so_far
}

fn main() {
    let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("{}", max_subarray_sum(&arr));
}

A 6

B 7

C 5

D 4

💡 Hint

Look for the contiguous subarray with the largest sum.

The maximum subarray is [4, -1, 2, 1] which sums to 6.

❓ Predict Output

intermediate

What is the maximum subarray sum for all negative numbers?

Given the array [-8, -3, -6, -2, -5, -4], what does Kadane's algorithm return as the maximum subarray sum?

DSA Rust

fn max_subarray_sum(nums: &[i32]) -> i32 {
    let mut max_ending_here = 0;
    let mut max_so_far = i32::MIN;
    for &x in nums {
        max_ending_here = (max_ending_here + x).max(x);
        max_so_far = max_so_far.max(max_ending_here);
    }
    max_so_far
}

fn main() {
    let arr = [-8, -3, -6, -2, -5, -4];
    println!("{}", max_subarray_sum(&arr));
}

A -3

B -5

C -2

D -4

💡 Hint

Kadane's algorithm returns the largest single element if all are negative.

The largest number in the array is -2, so the maximum subarray sum is -2.

🔧 Debug

advanced

What error occurs when running this Kadane's algorithm variant?

Consider this Rust code variant of Kadane's algorithm. What error will it produce when compiled or run?

DSA Rust

fn max_subarray_sum(nums: &[i32]) -> i32 {
    let mut max_ending_here = 0;
    let mut max_so_far = 0;
    for &x in nums {
        max_ending_here = (max_ending_here + x).max(x);
        max_so_far = max_so_far.max(max_ending_here);
    }
    max_so_far
}

fn main() {
    let arr = [-8, -3, -6, -2, -5, -4];
    println!("{}", max_subarray_sum(&arr));
}

A Runtime panic due to integer overflow

B Returns incorrect result 0 instead of -2

C Compilation error due to uninitialized variable

D Returns correct result -2

💡 Hint

Check initial value of max_so_far for correctness.

Initializing max_so_far to 0 causes it to ignore negative sums, leading to an incorrect maximum sum of 0 instead of -2.

🧠 Conceptual

advanced

What is the time complexity of Kadane's algorithm?

Kadane's algorithm finds the maximum subarray sum in an array. What is its time complexity?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

💡 Hint

The algorithm scans the array once.

Kadane's algorithm processes each element once, so it runs in linear time O(n).

🚀 Application

expert

How to modify Kadane's algorithm to return the subarray itself?

Which code snippet correctly modifies Kadane's algorithm to return the start and end indices of the maximum subarray along with the sum?

A Reset start and end indices to zero at each iteration regardless of max_ending_here.

B Use a separate array to store all subarrays and pick the max at the end.

C Only update end index when max_so_far changes; start index remains zero.

D Track temporary start index when max_ending_here resets; update start and end when max_so_far changes.

💡 Hint

Remember to track where the current subarray starts and update indices when max sum improves.

To find the subarray, track the start index when max_ending_here resets and update start/end when max_so_far updates.

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