Why Kadane's Algorithm Maximum Subarray in DSA Rust?

The Big Idea

What if you could find the best winning streak in your numbers without checking every possibility?

The Scenario

Imagine you have a list of daily profits and losses for your small business. You want to find the best continuous period where you made the most money. Doing this by checking every possible period manually would take forever!

The Problem

Manually checking every possible continuous period means looking at all start and end days. This takes a lot of time and is easy to mess up, especially if the list is long. It feels like searching for a needle in a haystack by hand.

The Solution

Kadane's Algorithm quickly finds the best continuous period by keeping track of the current profit and the best profit so far. It looks at each day once, deciding if adding that day helps or if starting fresh is better. This saves time and effort.

Before vs After

✗ Before

fn max_subarray_sum(nums: &[i32]) -> i32 {
    let mut max_sum = i32::MIN;
    for start in 0..nums.len() {
        let mut current_sum = 0;
        for end in start..nums.len() {
            current_sum += nums[end];
            if current_sum > max_sum {
                max_sum = current_sum;
            }
        }
    }
    max_sum
}

✓ After

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

What It Enables

This algorithm lets you quickly find the most profitable continuous period in any list of numbers, even if the list is very long.

Real Life Example

Stock traders use this to find the best time to buy and sell stocks by identifying the period with the highest gain.

Key Takeaways

Kadane's Algorithm finds the maximum sum of a continuous subarray efficiently.

It runs in linear time by scanning the list once.

It helps solve problems involving finding the best continuous segment quickly.

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