Kadane's Algorithm Maximum Subarray in DSA Go - Time & Space Complexity

Time Complexity: Kadane's Algorithm Maximum Subarray

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum sum of a continuous subarray changes as the input size grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the largest sum of any continuous subarray inside the given array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single loop through the array elements.
• How many times: Exactly once for each element in the array.

How Execution Grows With Input

As the array size grows, the number of steps grows directly in proportion.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the input size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum subarray sum grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Since we check sums of subarrays, it must be O(n²) because of nested loops."

[OK] Correct: Kadane's algorithm cleverly keeps track of sums as it goes, avoiding repeated work and nested loops.

Interview Connect

Understanding this linear-time solution shows you can find efficient answers to problems that seem complex at first, a key skill in interviews.

Self-Check

"What if we wanted to find the maximum subarray sum but also return the start and end indexes? How would the time complexity change?"

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