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

Concept Flow - Kadane's Algorithm Maximum Subarray

Start with first element

↓

Initialize current_sum and max_sum

↓

For each next element

↓

Update current_sum = max(element, current_sum + element)

↓

Update max_sum = max(max_sum, current_sum)

↓

Repeat until end of array

↓

Return max_sum

Kadane's algorithm scans the array once, keeping track of the best sum ending at each position and the overall best sum found.

Execution Sample

DSA C

int maxSubArray(int* nums, int numsSize) {
    int current_sum = nums[0];
    int max_sum = nums[0];
    for (int i = 1; i < numsSize; i++) {
        current_sum = (nums[i] > current_sum + nums[i]) ? nums[i] : current_sum + nums[i];
        max_sum = (max_sum > current_sum) ? max_sum : current_sum;
    }
    return max_sum;
}

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

Execution Table

Step	Operation	Index i	Current Element nums[i]	Current Sum	Max Sum	Subarray Considered
1	Initialize	0	-2	-2	-2	[-2]
2	Compare nums[1] and current_sum + nums[1]	1	1	max(1, -2+1)=1	max(-2,1)=1	[1]
3	Compare nums[2] and current_sum + nums[2]	2	-3	max(-3,1-3)=-2	max(1,-2)=1	[1,-3]
4	Compare nums[3] and current_sum + nums[3]	3	4	max(4,-2+4)=4	max(1,4)=4	[4]
5	Compare nums[4] and current_sum + nums[4]	4	-1	max(-1,4-1)=3	max(4,3)=4	[4,-1]
6	Compare nums[5] and current_sum + nums[5]	5	2	max(2,3+2)=5	max(4,5)=5	[4,-1,2]
7	Compare nums[6] and current_sum + nums[6]	6	1	max(1,5+1)=6	max(5,6)=6	[4,-1,2,1]
8	Compare nums[7] and current_sum + nums[7]	7	-5	max(-5,6-5)=1	max(6,1)=6	[4,-1,2,1,-5]
9	Compare nums[8] and current_sum + nums[8]	8	4	max(4,1+4)=5	max(6,5)=6	[4,-1,2,1,-5,4]
10	End of array	-	-	-	6	Maximum subarray sum found

💡 Reached end of array, max_sum = 6 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	-2	1	-2	4	3	5	6	1	5	5
max_sum	-2	1	1	4	4	5	6	6	6	6
i	0	1	2	3	4	5	6	7	8	-

Key Moments - 3 Insights

Why do we compare nums[i] with current_sum + nums[i] instead of just adding?

Because if current_sum + nums[i] is less than nums[i], starting fresh at nums[i] gives a better sum. See execution_table steps 2 and 4 where current_sum resets.

Why do we update max_sum after updating current_sum?

Because max_sum must always hold the best sum found so far, including the new current_sum. See execution_table steps 4 and 7 where max_sum updates after current_sum.

What happens if all numbers are negative?

Kadane's algorithm still works because it initializes current_sum and max_sum with the first element. The max_sum will be the largest (least negative) number. See step 1 initialization.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the current_sum value?

A 4

B -2

C 1

D 3

💡 Hint

Check the 'Current Sum' column at step 4 in execution_table.

At which step does max_sum first become 5?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Max Sum' column in execution_table and find when it changes to 5.

If the input array started with a large positive number instead of -2, how would current_sum change at step 1?

A It would be that large positive number

B It would remain -2

C It would be zero

D It would be the sum of first two elements

💡 Hint

current_sum initializes to nums[0], see variable_tracker 'Start' value.

Concept Snapshot

Kadane's Algorithm finds the maximum sum of a 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 to find the maximum sum of any contiguous subarray. It starts by setting current_sum and max_sum to the first element. Then, for each next element, it decides whether to add it to the current_sum or start fresh from that element, whichever is larger. After updating current_sum, it updates max_sum if current_sum is greater. This process continues until the end of the array, and max_sum holds the maximum subarray sum. The execution table shows each step with current_sum and max_sum values, and the variable tracker records their changes. Key moments clarify why comparisons are made and how the algorithm handles negative numbers. The visual quiz tests understanding of these steps.