Kadane's Algorithm Maximum Subarray in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of Kadane's algorithm on this array?

Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], what is the maximum subarray sum found by Kadane's algorithm?

DSA Go

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

func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    println(maxSubArray(nums))
}

A 6

B 7

C 5

D 4

💡 Hint

Think about the largest sum of a continuous subarray.

Kadane's algorithm finds the maximum sum of a contiguous subarray. Here, the subarray [4, -1, 2, 1] sums to 6, which is the maximum.

❓ Predict Output

intermediate

What is the maximum subarray sum for all negative numbers?

Given the array [-8, -3, -6, -2, -5, -4], what is the maximum subarray sum Kadane's algorithm returns?

DSA Go

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

func main() {
    nums := []int{-8, -3, -6, -2, -5, -4}
    println(maxSubArray(nums))
}

A -8

B -2

C -3

D 0

💡 Hint

Kadane's algorithm resets sum to zero when negative, but initial max is first element.

When all numbers are negative, Kadane's algorithm returns the largest single element, which is -2 here.

🔧 Debug

advanced

Why does this Kadane's algorithm implementation fail on all negative input?

Consider this code snippet for Kadane's algorithm. Why does it return 0 instead of the correct maximum subarray sum for all negative numbers? func maxSubArray(nums []int) int { maxSoFar := 0 maxEndingHere := 0 for _, num := range nums { maxEndingHere += num if maxEndingHere > maxSoFar { maxSoFar = maxEndingHere } if maxEndingHere < 0 { maxEndingHere = 0 } } return maxSoFar }

DSA Go

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

A maxEndingHere should not reset to 0 when negative.

B The function should return maxEndingHere instead of maxSoFar.

C maxSoFar initialized to 0 causes incorrect result for all negative numbers.

D Loop should start from second element, not first.

💡 Hint

Think about the initial value of maxSoFar and how it affects negative inputs.

Initializing maxSoFar to 0 causes the function to return 0 even when all numbers are negative, which is incorrect. It should start with the first element of the array.

🧠 Conceptual

advanced

What is the time complexity of Kadane's algorithm?

Kadane's algorithm finds the maximum sum of a contiguous subarray. What is its time complexity in terms of the input array size n?

A O(n)

B O(n^2)

C O(log n)

D O(n log n)

💡 Hint

Kadane's algorithm scans the array once.

Kadane's algorithm processes each element once, updating sums in constant time, so its time complexity is linear O(n).

🚀 Application

expert

Find the maximum subarray sum and the subarray itself

Modify Kadane's algorithm to return both the maximum sum and the actual subarray that produces this sum for the input array [3, -2, 5, -1]. What is the maximum sum and the subarray?

DSA Go

func maxSubArray(nums []int) (int, []int) {
    maxSoFar := nums[0]
    maxEndingHere := 0
    start := 0
    end := 0
    s := 0
    for i, num := range nums {
        maxEndingHere += num
        if maxEndingHere > maxSoFar {
            maxSoFar = maxEndingHere
            start = s
            end = i
        }
        if maxEndingHere < 0 {
            maxEndingHere = 0
            s = i + 1
        }
    }
    return maxSoFar, nums[start : end+1]
}

func main() {
    nums := []int{3, -2, 5, -1}
    maxSum, subarray := maxSubArray(nums)
    println(maxSum)
    for _, v := range subarray {
        print(v, " ")
    }
}

A Maximum sum: 3, Subarray: [3]

B Maximum sum: 7, Subarray: [3, -2, 5, -1]

C Maximum sum: 5, Subarray: [5]

D Maximum sum: 6, Subarray: [3, -2, 5]

💡 Hint

Track start and end indices when updating max sum.

The maximum sum is 6 from the subarray [3, -2, 5]. Adding -1 reduces the sum, so the best subarray ends before -1.

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