Kadane's Algorithm Maximum Subarray in DSA Rust

Mental Model

Find the largest sum of a continuous part of the list by keeping track of the best sum ending at each position.

Analogy: Imagine walking along a path with ups and downs in height; you want to find the highest hill segment you can stand on without jumping around.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Index:  0   1   2   3   4   5   6   7   8

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any continuous subarray

Step 1: Start with max_ending_here = max_so_far = -2 (first element)

max_ending_here = -2, max_so_far = -2

Why: Initialize with first element to start tracking sums

Step 2: Move to element 1: 1, update max_ending_here = max(1, -2 + 1) = 1, max_so_far = max(-2, 1) = 1

max_ending_here = 1, max_so_far = 1

Why: Either start new subarray at current element or continue previous

Step 3: Element 2: -3, max_ending_here = max(-3, 1 + -3) = -2, max_so_far = max(1, -2) = 1

max_ending_here = -2, max_so_far = 1

Why: Previous + current (-2) > current (-3), so continue previous subarray

Step 4: Element 3: 4, max_ending_here = max(4, -2 + 4) = 4, max_so_far = max(1, 4) = 4

max_ending_here = 4, max_so_far = 4

Why: Start new subarray at 4 because it improves sum

Step 5: Element 4: -1, max_ending_here = max(-1, 4 + -1) = 3, max_so_far = max(4, 3) = 4

max_ending_here = 3, max_so_far = 4

Why: Continue subarray since sum is still positive

Step 6: Element 5: 2, max_ending_here = max(2, 3 + 2) = 5, max_so_far = max(4, 5) = 5

max_ending_here = 5, max_so_far = 5

Why: Add positive number to increase sum

Step 7: Element 6: 1, max_ending_here = max(1, 5 + 1) = 6, max_so_far = max(5, 6) = 6

max_ending_here = 6, max_so_far = 6

Why: Keep adding to subarray to maximize sum

Step 8: Element 7: -5, max_ending_here = max(-5, 6 + -5) = 1, max_so_far = max(6, 1) = 6

max_ending_here = 1, max_so_far = 6

Why: Subarray sum drops but still positive, keep going

Step 9: Element 8: 4, max_ending_here = max(4, 1 + 4) = 5, max_so_far = max(6, 5) = 6

max_ending_here = 5, max_so_far = 6

Why: Add last element, max sum remains 6

Result:

Maximum subarray sum = 6

Annotated Code

DSA Rust

fn max_subarray_sum(nums: &[i32]) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    let mut max_ending_here = nums[0];
    let mut max_so_far = nums[0];
    for &num in &nums[1..] {
        max_ending_here = std::cmp::max(num, max_ending_here + num); // update max_ending_here
        max_so_far = std::cmp::max(max_so_far, max_ending_here); // update max_so_far
    }
    max_so_far
}

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

max_ending_here = std::cmp::max(num, max_ending_here + num); // update max_ending_here

Choose to start new subarray at current element or continue previous subarray

max_so_far = std::cmp::max(max_so_far, max_ending_here); // update max_so_far

Update global max if current subarray sum is better

Output

Maximum subarray sum = 6

Complexity Analysis

Time: O(n) because we scan the array once updating sums

Space: O(1) because we only keep track of two variables

vs Alternative: Naive approach checks all subarrays with O(n^2) or O(n^3) time, Kadane's is much faster

Edge Cases

empty array

returns 0 as no subarray exists

DSA Rust

if nums.is_empty() { return 0; }

all negative numbers

returns the largest (least negative) single element

DSA Rust

let mut max_ending_here = nums[0];

single element array

returns that element as max sum

DSA Rust

let mut max_ending_here = nums[0];

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray, reach for Kadane's algorithm because it efficiently tracks local and global sums in one pass.

Common Mistakes

Mistake: Resetting max_ending_here to zero instead of current element when sum drops below zero
Fix: Reset max_ending_here to current element to handle negative numbers correctly

Summary

Finds the maximum sum of any continuous subarray in a list.

Use when you need the largest sum of consecutive elements efficiently.

Keep track of the best sum ending at each position to avoid checking all subarrays.

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