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.