Kadane's Algorithm Maximum Subarray in DSA Rust - Build from Scratch

Kadane's Algorithm Maximum Subarray

📖 Scenario: Imagine you have a list of daily temperature changes. You want to find the longest period where the temperature increased the most in total. This helps you understand the best streak of warm days.

🎯 Goal: Build a Rust program that uses Kadane's Algorithm to find the maximum sum of a continuous subarray in a list of integers.

📋 What You'll Learn

Create a vector called changes with the exact values: [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]

Create a variable called max_ending_here and set it to 0

Create a variable called max_so_far and set it to the smallest possible integer value

Use a for loop with variable change to iterate over changes.iter()

Inside the loop, update max_ending_here by adding *change

If max_ending_here is less than 0, reset it to 0

If max_so_far is less than max_ending_here, update max_so_far to max_ending_here

Print the value of max_so_far

💡 Why This Matters

🌍 Real World

Finding the best continuous period of gains or improvements in data like stock prices, temperature changes, or sales.

💼 Career

Kadane's Algorithm is a classic technique used in software engineering and data analysis roles to efficiently solve maximum subarray problems.

1

Create the data vector

Create a vector called changes with these exact values: [3, -2, 5, -1, 6, -3, 2, 7, -5, 2]

DSA Rust

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

Hint

Use let changes = vec![...] to create the vector with the exact numbers.

2

Initialize helper variables

Create a variable called max_ending_here and set it to 0. Also create a variable called max_so_far and set it to i32::MIN (the smallest possible integer).

DSA Rust

fn main() {
    let changes = vec![3, -2, 5, -1, 6, -3, 2, 7, -5, 2];
    // Initialize max_ending_here and max_so_far
    // Your code here
}

Hint

Use let mut to create variables that can change. Use i32::MIN for the smallest integer.

3

Implement Kadane's Algorithm loop

Use a for loop with variable change to iterate over changes.iter(). Inside the loop, add *change to max_ending_here. If max_ending_here is less than 0, reset it to 0. If max_so_far is less than max_ending_here, update max_so_far to max_ending_here.

DSA Rust

fn main() {
    let changes = vec![3, -2, 5, -1, 6, -3, 2, 7, -5, 2];
    let mut max_ending_here = 0;
    let mut max_so_far = i32::MIN;

    // Loop over changes and update max_ending_here and max_so_far
    // Your code here
}

Hint

Use for change in changes.iter() to loop. Use *change to get the value from the reference.

4

Print the maximum subarray sum

Print the value of max_so_far using println!.

DSA Rust

fn main() {
    let changes = vec![3, -2, 5, -1, 6, -3, 2, 7, -5, 2];
    let mut max_ending_here = 0;
    let mut max_so_far = i32::MIN;

    for change in changes.iter() {
        max_ending_here += *change;
        if max_ending_here < 0 {
            max_ending_here = 0;
        }
        if max_so_far < max_ending_here {
            max_so_far = max_ending_here;
        }
    }

    // Print max_so_far
    // Your code here
}

Hint

Use println!("{}", max_so_far); to print the result.

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