Kadane's Algorithm Maximum Subarray in DSA Go - Deep Dive

Overview - Kadane's Algorithm Maximum Subarray

What is it?

Kadane's Algorithm is a way to find the largest sum of a continuous part of a list of numbers. It looks at each number and decides if adding it to the current sum helps or if starting fresh from that number is better. This helps find the maximum sum quickly without checking every possible part. It works even if the list has negative numbers.

Why it matters

Without Kadane's Algorithm, finding the largest sum of a continuous part would take a long time, especially for big lists, because you'd have to check all parts. This algorithm solves the problem fast and efficiently, saving time and computing power. It is useful in many real-world problems like stock trading, signal processing, and data analysis where quick decisions matter.

Where it fits

Before learning Kadane's Algorithm, you should understand arrays (lists of numbers) and basic loops. After this, you can explore related topics like divide and conquer methods for maximum subarray, dynamic programming, and other optimization algorithms.

Mental Model

Core Idea

At each step, decide whether to add the current number to the existing sum or start fresh from the current number to find the maximum continuous sum.

Think of it like...

Imagine walking along a path collecting coins. If the coins you find make your total less than starting fresh from the current spot, you drop what you have and start counting coins from here instead.

Index:    0    1    2    3    4    5
Array:   [−2,   1,  −3,   4,  −1,   2]

Step-by-step sums:
Current Sum:  -2   1   -2   4    3    5
Max Sum:      -2   1   1    4    4    5

At each index, choose max(current number, current sum + number)

Build-Up - 7 Steps

1

Foundation

Understanding the Maximum Subarray Problem

Concept: Introduce the problem of finding the largest sum of a continuous part of a list.

Given a list of numbers, we want to find a continuous section where the sum of numbers is as large as possible. For example, in [−2,1,−3,4,−1,2], the largest sum is 5 from the subarray [4,−1,2].

Result

Problem is clear: find the continuous part with the biggest sum.

Understanding the problem clearly is the first step to solving it efficiently.

2

Foundation

Brute Force Approach to Maximum Subarray

Concept: Check every possible continuous part and calculate their sums.

Try all subarrays by picking every start and end index, sum the numbers, and keep track of the largest sum found. This takes a lot of time because there are many subarrays.

Result

Correct answer but slow for big lists.

Knowing the brute force method helps appreciate why a faster method like Kadane's is needed.

3

Intermediate

Kadane's Algorithm Basic Idea

Concept: Use a running sum that resets when it becomes negative to find the max sum efficiently.

Keep a current sum starting at zero. For each number, add it to current sum. If current sum is less than the number itself, reset current sum to the number. Keep track of the maximum current sum seen so far.

Result

Finds maximum subarray sum in one pass through the list.

Knowing when to reset the sum avoids wasting time on negative sums that reduce the total.

4

Intermediate

Implementing Kadane's Algorithm in Go

Concept: Translate the algorithm into Go code with clear steps and comments.

package main import "fmt" func maxSubArray(nums []int) int { maxSoFar := nums[0] currentMax := nums[0] for i := 1; i < len(nums); i++ { if currentMax < 0 { currentMax = nums[i] } else { currentMax += nums[i] } if currentMax > maxSoFar { maxSoFar = currentMax } } return maxSoFar } func main() { nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4} fmt.Println(maxSubArray(nums)) }

Result

6

Seeing the code helps connect the idea to a working solution and understand the flow.

5

Intermediate

Self Check: Predict Kadane's Output

🤔Before reading on: Given the array [-2,1,-3,4,-1,2,1,-5,4], do you think Kadane's Algorithm returns 6 or 7? Commit to your answer.

Concept: Test understanding by predicting the output of Kadane's Algorithm on a sample input.

Run Kadane's Algorithm on the array step-by-step: - Start with -2 - Current max resets or adds each number - Track max so far The maximum sum subarray is [4, -1, 2, 1] with sum 6 or [4, -1, 2, 1, -5, 4] with sum 5? Check carefully.

Result

The correct maximum sum is 6 from subarray [4, -1, 2, 1].

Predicting output before seeing it strengthens understanding and memory.

6

Advanced

Handling All Negative Numbers

Concept: Kadane's Algorithm works even if all numbers are negative by initializing max values properly.

If all numbers are negative, the algorithm still finds the largest (least negative) number as the max subarray. This requires initializing maxSoFar and currentMax to the first element, not zero.

Result

Correct maximum sum even with all negatives, e.g. [-3, -5, -2] returns -2.

Proper initialization prevents errors and ensures the algorithm works in all cases.

7

Expert

Kadane's Algorithm for Maximum Subarray Indices

🤔Before reading on: Do you think Kadane's Algorithm can be easily modified to return the start and end indices of the max subarray? Commit to yes or no.

Concept: Extend Kadane's Algorithm to track the start and end positions of the maximum sum subarray.

Add variables to track the start index of the current sum and update the max subarray start and end indices when maxSoFar changes. This helps identify the exact subarray, not just the sum. Example code snippet: func maxSubArrayWithIndices(nums []int) (int, int, int) { maxSoFar := nums[0] currentMax := nums[0] start, end, tempStart := 0, 0, 0 for i := 1; i < len(nums); i++ { if currentMax < 0 { currentMax = nums[i] tempStart = i } else { currentMax += nums[i] } if currentMax > maxSoFar { maxSoFar = currentMax start = tempStart end = i } } return maxSoFar, start, end }

Result

Returns max sum and indices, e.g. (6, 3, 6) for input [-2,1,-3,4,-1,2,1,-5,4].

Tracking indices requires careful updates but adds valuable information for real applications.

Under the Hood

Kadane's Algorithm works by iterating through the list once, maintaining a running sum of the current subarray. If the running sum becomes negative, it resets to the current number because continuing with a negative sum would only reduce future sums. It keeps track of the maximum sum found so far. This approach uses the idea that a negative sum is never beneficial to keep when looking for a maximum sum subarray.

Why designed this way?

The algorithm was designed to reduce the time complexity from O(n^2) or O(n^3) in brute force methods to O(n) by avoiding redundant calculations. It leverages the insight that negative sums hurt the total, so resetting the sum is optimal. Alternatives like divide and conquer exist but are more complex and slower in practice.

Input Array:  [−2] [1] [−3] [4] [−1] [2] [1] [−5] [4]

Iteration:
CurrentSum:   -2 -> 1 -> -2 -> 4 -> 3 -> 5 -> 6 -> 1 -> 5
MaxSoFar:    -2 -> 1 -> 1 -> 4 -> 4 -> 5 -> 6 -> 6 -> 6

Reset when CurrentSum < 0:
At index 1: CurrentSum reset to 1
At index 3: CurrentSum reset to 4

MaxSoFar updated when CurrentSum > MaxSoFar.

Myth Busters - 3 Common Misconceptions

Quick: Does Kadane's Algorithm always find the maximum sum subarray even if all numbers are negative? Commit yes or no.

Common Belief: Kadane's Algorithm fails if all numbers are negative because it resets sums to zero.

Reality: Kadane's Algorithm works with all negative numbers if initialized properly with the first element, not zero.

Why it matters: Incorrect initialization causes wrong answers, missing the largest negative number as the max subarray.

Quick: Does Kadane's Algorithm find the maximum sum subarray by checking all possible subarrays? Commit yes or no.

Common Belief: Kadane's Algorithm checks every possible subarray to find the maximum sum.

Reality: Kadane's Algorithm uses a clever running sum and resets to avoid checking all subarrays, making it efficient.

Why it matters: Believing it checks all subarrays hides the efficiency and elegance of the algorithm.

Quick: Can Kadane's Algorithm be used to find the maximum product subarray without changes? Commit yes or no.

Common Belief: Kadane's Algorithm can be directly used to find the maximum product subarray.

Reality: Maximum product subarray requires a different approach because negative numbers and zeros affect products differently.

Why it matters: Using Kadane's Algorithm directly for product leads to wrong results and confusion.

Expert Zone

1

Kadane's Algorithm can be extended to track the start and end indices of the maximum subarray with minimal overhead.

2

The algorithm assumes a linear data structure; adapting it to circular arrays requires modifications.

3

In streaming data, Kadane's Algorithm can be adapted to find maximum subarrays in real-time with sliding windows.

When NOT to use

Kadane's Algorithm is not suitable when you need the maximum product subarray or when the array is circular and you want the maximum sum subarray that can wrap around. For those, use specialized algorithms like the maximum product subarray algorithm or modified Kadane's for circular arrays.

Production Patterns

Kadane's Algorithm is used in financial software to find best buy-sell periods, in signal processing to detect strongest signals, and in machine learning feature extraction to find important continuous patterns quickly.

Connections

Dynamic Programming

Kadane's Algorithm is a simple form of dynamic programming that builds solutions from previous results.

Understanding Kadane's helps grasp how dynamic programming breaks problems into smaller overlapping subproblems.

Sliding Window Technique

Both Kadane's and sliding window maintain a running calculation over a subset of data, but Kadane's resets based on sum negativity.

Knowing Kadane's clarifies when to reset or slide windows in other algorithms.

Financial Trading Analysis

Kadane's Algorithm models finding the best time to buy and sell stocks for maximum profit over continuous days.

Seeing Kadane's in finance shows how algorithms solve real-world optimization problems.

Common Pitfalls

#1 Initializing maxSoFar and currentMax to zero instead of the first element.

Wrong approach:

maxSoFar := 0
currentMax := 0

Correct approach:

maxSoFar := nums[0]
currentMax := nums[0]

Root cause:

Assuming sums start at zero ignores that all numbers could be negative, causing wrong max sum.

#2 Resetting currentMax to zero instead of the current number when currentMax is negative.

Wrong approach:

if currentMax < 0 {
currentMax = 0
}
currentMax += nums[i]

Correct approach:

if currentMax < 0 {
currentMax = nums[i]
} else {
currentMax += nums[i]
}

Root cause:

Resetting to zero loses the current number which might be larger than zero, leading to incorrect sums.

#3 Trying to use Kadane's Algorithm directly for maximum product subarray.

Wrong approach:

Use the same sum-based Kadane's logic for product without changes.

Correct approach:

Use a specialized algorithm that tracks max and min products at each step.

Root cause:

Misunderstanding that product behavior with negatives and zeros differs from sums.

Key Takeaways

Kadane's Algorithm finds the maximum sum of a continuous subarray efficiently in one pass.

It works by keeping a running sum and resetting it when the sum becomes negative to avoid reducing future sums.

Proper initialization with the first element is crucial to handle all negative numbers correctly.

The algorithm can be extended to track the start and end indices of the maximum subarray.

Kadane's Algorithm is a foundational example of dynamic programming and has many real-world applications.

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