Kadane's Algorithm Maximum Subarray in DSA Go - 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, keeping track of the best sum ending at each position and the overall best sum found.

Execution Sample

DSA Go

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxSubArray(arr []int) int {
    currentSum := arr[0]
    maxSum := arr[0]
    for i := 1; i < len(arr); i++ {
        currentSum = max(arr[i], currentSum + arr[i])
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

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

Execution Table

Step	Operation	Current Element	currentSum	maxSum	Visual State (Subarray)
1	Initialize	-2	-2	-2	[-2]
2	Process element	1	max(1, -2+1)=1	max(-2,1)=1	[1]
3	Process element	-3	max(-3, 1-3)=-2	max(1,-2)=1	[1,-3] discarded, currentSum reset to -2]
4	Process element	4	max(4, -2+4)=4	max(1,4)=4	[4]
5	Process element	-1	max(-1, 4-1)=3	max(4,3)=4	[4,-1]
6	Process element	2	max(2, 3+2)=5	max(4,5)=5	[4,-1,2]
7	Process element	1	max(1, 5+1)=6	max(5,6)=6	[4,-1,2,1]
8	Process element	-5	max(-5, 6-5)=1	max(6,1)=6	[4,-1,2,1,-5] but currentSum drops to 1]
9	Process element	4	max(4, 1+4)=5	max(6,5)=6	[4] or [4,-1,2,1,-5,4] partial, currentSum=5]
10	End	-	-	6	Maximum subarray sum found: 6

💡 Reached end of array, maxSum = 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
currentSum	-2	1	-2	4	3	5	6	1	5	5
maxSum	-2	1	1	4	4	5	6	6	6	6
current Element	-2	1	-3	4	-1	2	1	-5	4	-

Key Moments - 3 Insights

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

Because if adding the current element to the previous sum makes it smaller than the element alone, we start a new subarray from the current element. See execution_table rows 2, 3, and 4 where currentSum resets.

Why does maxSum sometimes stay the same even when currentSum changes?

maxSum only updates if currentSum is greater. For example, at step 3 currentSum drops to -2 but maxSum remains 1 (row 3). This ensures maxSum always holds the best sum found so far.

What happens if all numbers are negative?

Kadane's algorithm still works because it initializes currentSum and maxSum with the first element. It will pick the largest negative number as maxSum. This is shown in the first step initialization.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the value of currentSum?

A -2

B 4

C 1

D 3

💡 Hint

Check the 'currentSum' column in row 4 of the execution_table.

At which step does maxSum first become 6?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look at the 'maxSum' column in the execution_table rows 6 to 9.

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

A It would be negative

B It would be zero

C It would be that large positive number

D It would be unchanged

💡 Hint

Refer to variable_tracker 'currentSum' at Start and After Step 1.

Concept Snapshot

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

Full Transcript

Kadane's algorithm scans the array from start to end. It keeps track of the current sum of a subarray ending at the current position and the maximum sum found so far. At each step, it decides whether to add the current element to the existing subarray or start fresh from the current element if that is better. The maximum sum is updated if the current sum exceeds it. 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 of integers?

easy

A. The total sum of all elements

B. The minimum element in the array

C. The maximum sum of a contiguous subarray

D. The longest increasing subsequence

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 C

4. Quick Check:

   Maximum subarray sum = answer [OK]

Hint: Kadane's finds max sum in a continuous slice [OK]

Common Mistakes:

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

2. Which of the following is the correct initialization step in Kadane's Algorithm in Go?

easy

A. maxSoFar, maxEndingHere := 0, 0

B. maxSoFar, maxEndingHere := nums[0], nums[0]

C. maxSoFar, maxEndingHere := math.MinInt, 0

D. maxSoFar, maxEndingHere := 0, nums[0]

Solution

1. Step 1: Understand initialization in Kadane's Algorithm

   We start with the first element as both maxSoFar and maxEndingHere to handle negative numbers correctly.

2. Step 2: Analyze options

   maxSoFar, maxEndingHere := nums[0], nums[0] initializes both variables with the first element, which is the correct approach. Other options either use zero or math.MinInt incorrectly.

3. Final Answer:

   maxSoFar, maxEndingHere := nums[0], nums[0] -> Option B

4. Quick Check:

   Initialize with first element to handle negatives [OK]

Hint: Start max values with first array element [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes errors with all negatives
• Using math.MinInt without importing math package
• Starting maxEndingHere at 0 instead of first element

3. What is the output of the following Go code using Kadane's Algorithm?

func maxSubArray(nums []int) int {
    maxSoFar, maxEndingHere := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if maxEndingHere < 0 {
            maxEndingHere = nums[i]
        } else {
            maxEndingHere += nums[i]
        }
        if maxEndingHere > maxSoFar {
            maxSoFar = maxEndingHere
        }
    }
    return maxSoFar
}

fmt.Println(maxSubArray([]int{-2,1,-3,4,-1,2,1,-5,4}))

medium

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Trace the iteration and update maxEndingHere and maxSoFar

   Start with maxSoFar = -2, maxEndingHere = -2.
   i=1: maxEndingHere < 0, so maxEndingHere=1; maxSoFar=1
   i=2: maxEndingHere=1+(-3)=-2; maxSoFar=1
   i=3: maxEndingHere<0, maxEndingHere=4; maxSoFar=4
   i=4: maxEndingHere=4+(-1)=3; maxSoFar=4
   i=5: maxEndingHere=3+2=5; maxSoFar=5
   i=6: maxEndingHere=5+1=6; maxSoFar=6
   i=7: maxEndingHere=6+(-5)=1; maxSoFar=6
   i=8: maxEndingHere=1+4=5; maxSoFar=6

2. Step 2: Determine final maxSoFar

   After loop, maxSoFar is 6, which is the maximum subarray sum.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Track maxEndingHere and maxSoFar updates carefully [OK]

Common Mistakes:

• Adding negative numbers without reset
• Not updating maxSoFar correctly
• Starting loop from 0 instead of 1

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

func maxSubArray(nums []int) int {
    maxSoFar, maxEndingHere := 0, 0
    for _, num := range nums {
        maxEndingHere = max(num, maxEndingHere + num)
        maxSoFar = max(maxSoFar, maxEndingHere)
    }
    return maxSoFar
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

medium

A. maxSoFar and maxEndingHere should start at nums[0], not 0

B. The max function is incorrectly implemented

C. The loop should start from index 1, not 0

D. The function should return maxEndingHere instead of maxSoFar

Solution

1. Step 1: Check initialization of maxSoFar and maxEndingHere

   Initializing both to 0 causes wrong results if all numbers are negative because maxSoFar starts too low.

2. Step 2: Correct initialization

   They should be initialized to nums[0] to correctly handle negative values and start with the first element.

3. Final Answer:

   maxSoFar and maxEndingHere should start at nums[0], not 0 -> Option A

4. Quick Check:

   Initialize with first element to handle negatives [OK]

Hint: Initialize max values with first element, not zero [OK]

Common Mistakes:

• Starting maxSoFar at 0 causes wrong max for negatives
• Confusing maxSoFar and maxEndingHere roles
• Returning wrong variable at end

5. Given an array of integers, how would you modify Kadane's Algorithm to also return the start and end indices of the maximum sum subarray?

hard

A. Track start index when maxEndingHere resets; update end index when maxSoFar changes

B. Store all subarrays and pick the max at the end

C. Use a nested loop to check all subarrays and track indices

D. Keep a count of positive numbers and return their indices

Solution

1. Step 1: Understand how to track indices in Kadane's Algorithm

   When maxEndingHere resets to current element, record that index as potential start. When maxSoFar updates, record current index as end.

2. Step 2: Compare with other options

   Store all subarrays and pick the max at the end and C are brute force and inefficient. Keep a count of positive numbers and return their indices is unrelated to max subarray indices.

3. Final Answer:

   Track start index when maxEndingHere resets; update end index when maxSoFar changes -> Option A

4. Quick Check:

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

Hint: Update start on reset, end on max update [OK]

Common Mistakes:

• Not updating start index when resetting maxEndingHere
• Using nested loops instead of Kadane's approach
• Ignoring indices and returning only sum