Kadane's Algorithm Maximum Subarray in DSA Rust - Execution Trace

Concept Flow - Kadane's Algorithm Maximum Subarray

Start

↓

Initialize max_so_far = arr[0

↓

For each element x in array

↓

Add x to max_ending_here

↓

If max_ending_here < 0?

Yes→Reset max_ending_here = 0

No↓

If max_so_far < max_ending_here?

Yes→Update max_so_far = max_ending_here

↓

Repeat for next element

↓

End: max_so_far is max subarray sum

The algorithm scans the array, adding elements to a running sum. If the sum drops below zero, it resets. It keeps track of the highest sum found.

Execution Sample

DSA Rust

fn max_subarray(arr: &[i32]) -> i32 {
    let mut max_so_far = arr[0];
    let mut max_ending_here = 0;
    for &x in arr {
        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;
        }
    }
    max_so_far
}

This code finds the maximum sum of any continuous subarray using Kadane's algorithm.

Execution Table

Step	Operation	Current Element (x)	max_ending_here Before	max_ending_here After	max_so_far Before	max_so_far After	Visual State (max_ending_here, max_so_far)
1	Initialize	-	-	0	-	1	(0, 1)
2	Add x to max_ending_here	1	0	1	1	1	(1, 1)
3	Check max_ending_here < 0	1	1	1	1	1	(1, 1)
4	Update max_so_far if needed	1	1	1	1	1	(1, 1)
5	Add x to max_ending_here	-2	1	-1	1	1	(-1, 1)
6	Check max_ending_here < 0	-2	-1	0	1	1	(0, 1)
7	Update max_so_far if needed	-2	0	0	1	1	(0, 1)
8	Add x to max_ending_here	3	0	3	1	1	(3, 1)
9	Check max_ending_here < 0	3	3	3	1	1	(3, 1)
10	Update max_so_far if needed	3	3	3	1	3	(3, 3)
11	Add x to max_ending_here	4	3	7	3	3	(7, 3)
12	Check max_ending_here < 0	4	7	7	3	3	(7, 3)
13	Update max_so_far if needed	4	7	7	3	7	(7, 7)
14	Add x to max_ending_here	-1	7	6	7	7	(6, 7)
15	Check max_ending_here < 0	-1	6	6	7	7	(6, 7)
16	Update max_so_far if needed	-1	6	6	7	7	(6, 7)
17	Add x to max_ending_here	2	6	8	7	7	(8, 7)
18	Check max_ending_here < 0	2	8	8	7	7	(8, 7)
19	Update max_so_far if needed	2	8	8	7	8	(8, 8)
20	Add x to max_ending_here	1	8	9	8	8	(9, 8)
21	Check max_ending_here < 0	1	9	9	8	8	(9, 8)
22	Update max_so_far if needed	1	9	9	8	9	(9, 9)
23	Add x to max_ending_here	-5	9	4	9	9	(4, 9)
24	Check max_ending_here < 0	-5	4	4	9	9	(4, 9)
25	Update max_so_far if needed	-5	4	4	9	9	(4, 9)
26	Add x to max_ending_here	4	4	8	9	9	(8, 9)
27	Check max_ending_here < 0	4	8	8	9	9	(8, 9)
28	Update max_so_far if needed	4	8	8	9	9	(8, 9)
29	End	-	-	-	-	9	Max subarray sum = 9

💡 Reached end of array, max_so_far holds the maximum subarray sum

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 14	After Step 17	After Step 20	After Step 23	After Step 26	Final
max_ending_here	0	1	0	3	7	6	8	9	4	8	8
max_so_far	1	1	1	3	7	7	8	9	9	9	9

Key Moments - 3 Insights

Why do we reset max_ending_here to 0 when it becomes negative?

Because a negative sum will only reduce the sum of any future subarray. Resetting to 0 allows starting fresh from the next element. See steps 5-6 where max_ending_here goes from -1 to 0.

Why do we initialize max_so_far with the first element instead of 0?

Because the array might contain all negative numbers, and max_so_far should reflect the maximum element found so far. Initializing with arr[0] ensures correctness. See step 1 initialization.

What happens if all elements are negative?

In this implementation, max_ending_here resets to 0 often, but max_so_far keeps track of the largest element. So the result will be the maximum single element. This is why max_so_far starts at arr[0].

Visual Quiz - 3 Questions

Look at the execution_table at step 17, what is max_ending_here after adding the element?

A 7

B 8

C 6

D 9

💡 Hint

Check the 'max_ending_here After' column at step 17 in the execution_table.

At which step does max_so_far first update to 7?

A Step 17

B Step 10

C Step 13

D Step 22

💡 Hint

Look at the 'max_so_far After' column and find when it changes from 3 to 7.

If we remove the reset of max_ending_here to 0 when negative, what would happen to max_so_far?

A It might become smaller than actual max subarray sum

B It would always be zero

C It would still be correct

D It would become the sum of the entire array

💡 Hint

Consider how negative sums affect the running total and max_so_far updates in the execution_table.

Concept Snapshot

Kadane's Algorithm finds the max sum of a continuous subarray.
Initialize max_so_far = first element, max_ending_here = 0.
Add each element to max_ending_here.
If max_ending_here < 0, reset to 0.
Update max_so_far if max_ending_here is greater.
Result: max_so_far is max subarray sum.

Full Transcript

Kadane's Algorithm scans the array from start to end. It keeps a running sum called max_ending_here. When adding the current element, if max_ending_here becomes negative, it resets to zero to avoid reducing future sums. It also keeps track of the highest sum found so far in max_so_far. This way, it finds the maximum sum of any continuous subarray efficiently in one pass.

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