Kadane's Algorithm Maximum Subarray in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the maximum sum with the first element of the array.

DSA Go

maxSoFar := nums[[1]]

Drag options to blanks, or click blank then click option'

Alen(nums)

B0

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as the index which causes skipping the first element.

Using len(nums) which is out of range.

We start with the first element at index 0 as the initial maximum sum.

2fill in blank

medium

Complete the code to update the current sum by choosing the maximum between the current number and the sum plus current number.

DSA Go

currentSum = max(nums[i], currentSum [1] nums[i])

Drag options to blanks, or click blank then click option'

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Using division which is not meaningful here.

We add the current number to the current sum or start fresh from the current number, whichever is larger.

3fill in blank

hard

Fix the error in the max function to correctly return the larger of two integers.

DSA Go

func max(a, b int) int {
    if a [1] b {
        return a
    }
    return b
}

Drag options to blanks, or click blank then click option'

A==

B<

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' which returns the smaller value.

Using '==' or '!=' which do not compare size.

The function should return 'a' if 'a' is greater than 'b'.

4fill in blank

hard

Fill both blanks to update maxSoFar if currentSum is greater.

DSA Go

if currentSum [1] maxSoFar {
    maxSoFar = [2]
}

Drag options to blanks, or click blank then click option'

A>

B<

CcurrentSum

DmaxSoFar

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' which reverses the logic.

Assigning maxSoFar to itself instead of currentSum.

If currentSum is greater than maxSoFar, update maxSoFar to currentSum.

5fill in blank

hard

Fill all three blanks to complete the Kadane's algorithm function.

DSA Go

func maxSubArray(nums []int) int {
    maxSoFar := nums[[1]]
    currentSum := nums[0]
    for i := 1; i < [2]; i++ {
        currentSum = max(nums[i], currentSum [3] nums[i])
        if currentSum > maxSoFar {
            maxSoFar = currentSum
        }
    }
    return maxSoFar
}

Drag options to blanks, or click blank then click option'

A0

Blen(nums)

C+

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 0 causing double count.

Using subtraction or other operators instead of addition.

Start maxSoFar at index 0, loop until length of nums, and add currentSum plus nums[i].

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