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

Concept Flow - Kadane's Algorithm Maximum Subarray

Start with first element

↓

Initialize current_sum and max_sum

↓

For each next element in array

↓

Update current_sum = max(element, current_sum + element)

↓

Update max_sum = max(max_sum, current_sum)

↓

Repeat until end of array

↓

Return max_sum as max subarray sum

Kadane's algorithm scans the array once, keeping track of the current subarray sum and the maximum sum found so far.

Execution Sample

DSA Python

arr = [1, -2, 3, 4, -1, 2, 1, -5, 4]
current_sum = max_sum = arr[0]
for x in arr[1:]:
    current_sum = max(x, current_sum + x)
    max_sum = max(max_sum, current_sum)
print(max_sum)

This code finds the maximum sum of any contiguous subarray in the given array.

Execution Table

Step	Operation	Current Element	current_sum	max_sum	Explanation
1	Initialize	1	1	1	Start with first element as current_sum and max_sum
2	Process element	-2	-1	1	current_sum = max(-2, 1 + -2) = -1; max_sum stays 1
3	Process element	3	3	3	current_sum = max(3, -1 + 3) = 3; max_sum updated to 3
4	Process element	4	7	7	current_sum = max(4, 3 + 4) = 7; max_sum updated to 7
5	Process element	-1	6	7	current_sum = max(-1, 7 + -1) = 6; max_sum stays 7
6	Process element	2	8	8	current_sum = max(2, 6 + 2) = 8; max_sum updated to 8
7	Process element	1	9	9	current_sum = max(1, 8 + 1) = 9; max_sum updated to 9
8	Process element	-5	4	9	current_sum = max(-5, 9 + -5) = 4; max_sum stays 9
9	Process element	4	8	9	current_sum = max(4, 4 + 4) = 8; max_sum stays 9
10	End	N/A	N/A	9	Reached end of array, max_sum is final result

💡 All elements processed, max_sum = 9 is the maximum subarray sum

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
current_sum	1	-1	3	7	6	8	9	4	8	N/A
max_sum	1	1	3	7	7	8	9	9	9	9
current_element	1	-2	3	4	-1	2	1	-5	4	N/A

Key Moments - 3 Insights

Why do we compare current element with current_sum + element when updating current_sum?

Because if current_sum + element is less than the element alone, starting fresh from current element gives a better sum. See execution_table rows 2 and 3 where current_sum resets.

Why does max_sum sometimes stay the same even when current_sum changes?

max_sum only updates if current_sum is greater. For example, at step 5 current_sum decreases but max_sum remains 7 as it is still the highest found so far.

What happens if all elements are negative?

Kadane's algorithm still works because it picks the maximum single element as max_sum. The logic of max(x, current_sum + x) ensures this. This is implied by initialization in step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of current_sum?

A 4

B 7

C 3

D 6

💡 Hint

Check the 'current_sum' column in execution_table row 4

At which step does max_sum first update to 9?

A Step 9

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'max_sum' column in execution_table rows 6 to 9

If the array started with a large negative number instead of 1, how would current_sum update at step 2?

A It would reset to the current element if larger than sum plus element

B It would always add the current element to previous sum

C It would stay the same as initial value

D It would become zero

💡 Hint

Refer to the logic in execution_table row 2 where current_sum is max(x, current_sum + x)

Concept Snapshot

Kadane's Algorithm finds max sum of contiguous subarray
Initialize current_sum and max_sum with first element
For each element, update current_sum = max(element, current_sum + element)
Update max_sum = max(max_sum, current_sum)
Return max_sum after processing all elements

Full Transcript

Kadane's algorithm scans the array once. It keeps two values: current_sum which tracks the sum of the current subarray being considered, and max_sum which tracks the highest sum found so far. Starting from the first element, for each next element, it decides whether to add it to the current_sum or start fresh from that element if it is larger alone. Then it updates max_sum if current_sum is higher. This way, it finds the maximum sum of any contiguous subarray efficiently in one pass.

Practice

1. What does Kadane's Algorithm primarily help to find in an array?

easy

A. The longest increasing subsequence

B. The minimum element in the array

C. The total sum of all elements

D. The maximum sum of a contiguous subarray

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of any contiguous subarray within a given array.

2. Step 2: Compare with other options

   Options B, C, and D describe different problems unrelated to Kadane's Algorithm.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option D

4. Quick Check:

   Maximum subarray sum = maximum sum of contiguous elements [OK]

Hint: Kadane finds max sum in continuous parts of array [OK]

Common Mistakes:

• Confusing maximum subarray sum with total array sum
• Thinking it finds minimum or longest subsequence
• Assuming it sorts the array

2. Which of the following is the correct initialization for Kadane's Algorithm variables in Python?

easy

A. max_so_far = 0; max_ending_here = float('inf')

B. max_so_far = 0; max_ending_here = 0

C. max_so_far = float('-inf'); max_ending_here = 0

D. max_so_far = null; max_ending_here = null

Solution

1. Step 1: Understand variable roles in Kadane's Algorithm

   max_so_far tracks the maximum sum found so far, so it should start very low (negative infinity) to handle negative numbers. max_ending_here tracks current subarray sum and starts at 0.

2. Step 2: Check each option

   max_so_far = 0; max_ending_here = 0 initializes max_so_far to 0, which fails if all numbers are negative. max_so_far = 0; max_ending_here = float('inf') wrongly sets max_ending_here to positive infinity. max_so_far = null; max_ending_here = null uses null, which causes errors in arithmetic.

3. Final Answer:

   max_so_far = float('-inf'); max_ending_here = 0 -> Option C

4. Quick Check:

   Initialize max_so_far very low, max_ending_here zero [OK]

Hint: Start max_so_far very low to handle negatives [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results with negatives
• Using null causes type errors
• Setting max_ending_here to infinity breaks logic

3. What is the output of the following code?

def max_subarray_sum(arr):
    max_so_far = float('-inf')
    max_ending_here = 0
    for x in arr:
        max_ending_here += x
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

print(max_subarray_sum([-2, 3, 2, -1, 4, -5]))

medium

A. 8

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace the loop and update sums

   Start max_so_far = float('-inf'), max_ending_here = 0
   Iteration 1: x=-2, max_ending_here= -2; max_so_far updated to -2; -2<0 reset to 0 (max_so_far=-2)
   Iteration 2: x=3, max_ending_here=3 > -2, max_so_far=3
   Iteration 3: x=2, max_ending_here=5 >3, max_so_far=5
   Iteration 4: x=-1, max_ending_here=4 <5 no update, 4>=0 no reset
   Iteration 5: x=4, max_ending_here=8 >5, max_so_far=8
   Iteration 6: x=-5, max_ending_here=3 <8 no update, 3>=0 no reset

2. Step 2: Final return value

   max_so_far is 8, so the function returns 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Max subarray sum = 8 [OK]

Hint: Add elements, reset sum if negative, track max sum [OK]

Common Mistakes:

• Not resetting max_ending_here when negative
• Updating max_so_far incorrectly
• Miscounting sums during iteration

4. Identify the bug in this Kadane's Algorithm implementation:

def max_subarray(arr):
    max_so_far = 0
    max_ending_here = 0
    for i in range(len(arr)):
        max_ending_here = max_ending_here + arr[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
        elif max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

print(max_subarray([-3, -2, -1]))

medium

A. max_so_far initialized to 0 causes wrong result for all negatives

B. Using elif instead of if causes skipping reset of max_ending_here

C. Loop should start from 1, not 0

D. max_ending_here should be initialized to float('-inf')

Solution

1. Step 1: Trace execution on [-3, -2, -1]

   max_so_far=0, max_ending_here=0.
   i=0, x=-3: meh=-3; 0 < -3? no; elif -3<0: yes, meh=0.
   i=1, x=-2: meh=-2; no update; reset meh=0.
   i=2, x=-1: meh=-1; no update; reset.
   Returns 0, but correct max subarray sum is -1.

2. Step 2: Why A and not others

   Init max_so_far=0 prevents update when all negative (meh never >0). B: elif ok here (if never true, always resets). C: range correct. D: meh=0 correct.

3. Final Answer:

   max_so_far initialized to 0 causes wrong result for all negatives -> Option A

4. Quick Check:

   Init max_so_far to float('-inf') for negatives [OK]

Hint: Initialize max_so_far to float('-inf') to handle all-negative arrays [OK]

Common Mistakes:

• Initializing max_so_far to 0 fails with all negatives
• Using elif causes reset to be skipped
• Wrong loop range causes index errors

5. Given an array of integers, how can Kadane's Algorithm be adapted to also return the start and end indices of the maximum sum subarray?
Choose the best approach.

hard

A. Use a nested loop to check all subarrays and record indices

B. Track current start index when resetting max_ending_here; update global start and end when max_so_far changes

C. Store all subarrays and pick the max sum after the loop ends

D. Return max_so_far only; indices cannot be found with Kadane's Algorithm

Solution

1. Step 1: Understand Kadane's Algorithm extension

   To find indices, track the start index of the current subarray when max_ending_here resets to 0. When max_so_far updates, record current start and end indices.

2. Step 2: Compare with other options

   Store all subarrays and pick the max sum after the loop ends is inefficient and not Kadane's approach. Use a nested loop to check all subarrays and record indices is brute force, not Kadane's. Return max_so_far only; indices cannot be found with Kadane's Algorithm is incorrect; indices can be found.

3. Final Answer:

   Track current start index when resetting max_ending_here; update global start and end when max_so_far changes -> Option B

4. Quick Check:

   Track start on reset, update indices on max update [OK]

Hint: Track start index on reset, update when max_so_far changes [OK]

Common Mistakes:

• Ignoring index tracking in Kadane's Algorithm
• Using brute force instead of Kadane's logic
• Assuming indices can't be found with Kadane's