Kadane's Algorithm Maximum Subarray in DSA Go - Build from Scratch

Kadane's Algorithm Maximum Subarray

📖 Scenario: You are analyzing daily temperature changes to find the longest period of warming. You have a list of temperature changes, and you want to find the maximum sum of consecutive days where the temperature increased.

🎯 Goal: Build a Go program that uses Kadane's Algorithm to find the maximum sum of a contiguous subarray in a list of integers representing daily temperature changes.

📋 What You'll Learn

Create a slice called changes with the exact values: [-2, 3, 2, -1, 4, -5, 2]

Create an integer variable called maxSoFar and set it to the first element of changes

Create an integer variable called maxEndingHere and set it to the first element of changes

Use a for loop with variable i starting from 1 to iterate over changes

Inside the loop, update maxEndingHere to the maximum of changes[i] and maxEndingHere + changes[i]

Inside the loop, update maxSoFar to the maximum of maxSoFar and maxEndingHere

Print the value of maxSoFar after the loop

💡 Why This Matters

🌍 Real World

Finding the longest warming period or maximum gain in stock prices involves finding the maximum sum of consecutive changes, which Kadane's Algorithm efficiently solves.

💼 Career

Kadane's Algorithm is a classic technique used in software engineering interviews and real-world problems involving arrays and optimization.

1

Create the data slice

Create a slice called changes with the exact values: []int{-2, 3, 2, -1, 4, -5, 2}

DSA Go

package main

func main() {
    // Create the slice changes with values -2, 3, 2, -1, 4, -5, 2
    // Your code here
}

Hint

Use changes := []int{...} to create the slice with the exact values.

2

Initialize variables for Kadane's Algorithm

Create two integer variables called maxSoFar and maxEndingHere and set both to the first element of changes

DSA Go

package main

import "fmt"

func main() {
    changes := []int{-2, 3, 2, -1, 4, -5, 2}
    // Initialize maxSoFar and maxEndingHere to changes[0]
    // Your code here
}

Hint

Set both variables to changes[0] to start Kadane's Algorithm.

3

Implement the core Kadane's Algorithm loop

Use a for loop with variable i starting from 1 to iterate over changes. Inside the loop, update maxEndingHere to the maximum of changes[i] and maxEndingHere + changes[i]. Then update maxSoFar to the maximum of maxSoFar and maxEndingHere. Use if statements to compare values.

DSA Go

package main

import "fmt"

func main() {
    changes := []int{-2, 3, 2, -1, 4, -5, 2}
    maxSoFar := changes[0]
    maxEndingHere := changes[0]
    // Loop from i = 1 to end of changes
    // Update maxEndingHere and maxSoFar inside the loop
    // Your code here
}

Hint

Use for i := 1; i < len(changes); i++ to loop. Use if to update maxEndingHere and maxSoFar.

4

Print the maximum subarray sum

Print the value of maxSoFar using fmt.Println(maxSoFar) after the loop

DSA Go

package main

import "fmt"

func main() {
    changes := []int{-2, 3, 2, -1, 4, -5, 2}
    maxSoFar := changes[0]
    maxEndingHere := changes[0]

    for i := 1; i  maxEndingHere+changes[i] {
            maxEndingHere = changes[i]
        } else {
            maxEndingHere = maxEndingHere + changes[i]
        }

        if maxEndingHere > maxSoFar {
            maxSoFar = maxEndingHere
        }
    }
    // Print maxSoFar
    // Your code here
}

Hint

Use fmt.Println(maxSoFar) to print the result.

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