Kadane's Algorithm Maximum Subarray in DSA Python

Mental Model

Find the largest sum of a continuous part of the list by keeping track of the best sum ending at each position.

Analogy: Imagine walking along a path with ups and downs in height. You want to find the highest hill you can climb without going back, by deciding at each step whether to continue climbing or start fresh from that point.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Index:  0   1   2   3   4   5   6   7   8

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any continuous subarray

Step 1: Start with first element: current_sum = max_sum = -2

current_sum = -2, max_sum = -2

Why: Initialize sums with first element to start tracking

Step 2: Move to element 1: current_sum = max(1, -2 + 1) = 1; max_sum = max(-2, 1) = 1

current_sum = 1, max_sum = 1

Why: Decide to start new subarray at 1 because it is better than continuing

Step 3: Element 2: current_sum = max(-3, 1 + -3) = -2; max_sum = max(1, -2) = 1

current_sum = -2, max_sum = 1

Why: Continuing subarray lowers sum, but max_sum stays the same

Step 4: Element 3: current_sum = max(4, -2 + 4) = 4; max_sum = max(1, 4) = 4

current_sum = 4, max_sum = 4

Why: Start new subarray at 4 because it is better than continuing

Step 5: Element 4: current_sum = max(-1, 4 + -1) = 3; max_sum = max(4, 3) = 4

current_sum = 3, max_sum = 4

Why: Continue subarray, max_sum unchanged

Step 6: Element 5: current_sum = max(2, 3 + 2) = 5; max_sum = max(4, 5) = 5

current_sum = 5, max_sum = 5

Why: Continue subarray, max_sum updated

Step 7: Element 6: current_sum = max(1, 5 + 1) = 6; max_sum = max(5, 6) = 6

current_sum = 6, max_sum = 6

Why: Continue subarray, max_sum updated

Step 8: Element 7: current_sum = max(-5, 6 + -5) = 1; max_sum = max(6, 1) = 6

current_sum = 1, max_sum = 6

Why: Subarray sum drops, max_sum unchanged

Step 9: Element 8: current_sum = max(4, 1 + 4) = 5; max_sum = max(6, 5) = 6

current_sum = 5, max_sum = 6

Why: Continue subarray, max_sum unchanged

Result:

Maximum subarray sum = 6

Annotated Code

DSA Python

from typing import List

class Solution:
    def max_subarray(self, nums: List[int]) -> int:
        current_sum = max_sum = nums[0]
        for i in range(1, len(nums)):
            # Decide to start new subarray or continue
            current_sum = max(nums[i], current_sum + nums[i])
            # Update max_sum if current_sum is better
            max_sum = max(max_sum, current_sum)
        return max_sum

if __name__ == "__main__":
    arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    sol = Solution()
    print(sol.max_subarray(arr))

current_sum = max(nums[i], current_sum + nums[i])

Choose to start new subarray at current element or continue previous subarray

max_sum = max(max_sum, current_sum)

Update max_sum if current_sum is larger

Output

6

Complexity Analysis

Time: O(n) because we scan the array once, updating sums at each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Better than checking all subarrays (O(n^2)) because it avoids repeated sums by using running totals

Edge Cases

Array with one element

Returns that element as max sum

DSA Python

current_sum = max_sum = nums[0]

All negative numbers

Returns the largest (least negative) single element

DSA Python

current_sum = max(nums[i], current_sum + nums[i])

Array with all positive numbers

Returns sum of entire array

DSA Python

max_sum = max(max_sum, current_sum)

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray, reach for Kadane's algorithm because it efficiently tracks sums without checking all subarrays.

Common Mistakes

Mistake: Resetting current_sum to zero instead of current element when current_sum becomes negative
Fix: Use max(nums[i], current_sum + nums[i]) to decide whether to start new subarray at current element

Mistake: Not updating max_sum after each step
Fix: Always update max_sum with max(max_sum, current_sum) inside the loop

Summary

Finds the maximum sum of any continuous subarray in a list.

Use when you need the largest sum of consecutive elements efficiently.

Keep track of the best sum ending at each position to avoid checking all subarrays.

Practice

1. What does Kadane's Algorithm primarily help to find in an array?

easy

A. The longest increasing subsequence

B. The minimum element in the array

C. The total sum of all elements

D. The maximum sum of a contiguous subarray

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 D

4. Quick Check:

   Maximum subarray sum = maximum sum of contiguous elements [OK]

Hint: Kadane finds max sum in continuous parts of array [OK]

Common Mistakes:

• Confusing maximum subarray sum with total array sum
• Thinking it finds minimum or longest subsequence
• Assuming it sorts the array

2. Which of the following is the correct initialization for Kadane's Algorithm variables in Python?

easy

A. max_so_far = 0; max_ending_here = float('inf')

B. max_so_far = 0; max_ending_here = 0

C. max_so_far = float('-inf'); max_ending_here = 0

D. max_so_far = null; max_ending_here = null

Solution

1. Step 1: Understand variable roles in Kadane's Algorithm

   max_so_far tracks the maximum sum found so far, so it should start very low (negative infinity) to handle negative numbers. max_ending_here tracks current subarray sum and starts at 0.

2. Step 2: Check each option

   max_so_far = 0; max_ending_here = 0 initializes max_so_far to 0, which fails if all numbers are negative. max_so_far = 0; max_ending_here = float('inf') wrongly sets max_ending_here to positive infinity. max_so_far = null; max_ending_here = null uses null, which causes errors in arithmetic.

3. Final Answer:

   max_so_far = float('-inf'); max_ending_here = 0 -> Option C

4. Quick Check:

   Initialize max_so_far very low, max_ending_here zero [OK]

Hint: Start max_so_far very low to handle negatives [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results with negatives
• Using null causes type errors
• Setting max_ending_here to infinity breaks logic

3. What is the output of the following code?

def max_subarray_sum(arr):
    max_so_far = float('-inf')
    max_ending_here = 0
    for x in arr:
        max_ending_here += x
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

print(max_subarray_sum([-2, 3, 2, -1, 4, -5]))

medium

A. 8

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace the loop and update sums

   Start max_so_far = float('-inf'), max_ending_here = 0
   Iteration 1: x=-2, max_ending_here= -2; max_so_far updated to -2; -2<0 reset to 0 (max_so_far=-2)
   Iteration 2: x=3, max_ending_here=3 > -2, max_so_far=3
   Iteration 3: x=2, max_ending_here=5 >3, max_so_far=5
   Iteration 4: x=-1, max_ending_here=4 <5 no update, 4>=0 no reset
   Iteration 5: x=4, max_ending_here=8 >5, max_so_far=8
   Iteration 6: x=-5, max_ending_here=3 <8 no update, 3>=0 no reset

2. Step 2: Final return value

   max_so_far is 8, so the function returns 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Max subarray sum = 8 [OK]

Hint: Add elements, reset sum if negative, track max sum [OK]

Common Mistakes:

• Not resetting max_ending_here when negative
• Updating max_so_far incorrectly
• Miscounting sums during iteration

4. Identify the bug in this Kadane's Algorithm implementation:

def max_subarray(arr):
    max_so_far = 0
    max_ending_here = 0
    for i in range(len(arr)):
        max_ending_here = max_ending_here + arr[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
        elif max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

print(max_subarray([-3, -2, -1]))

medium

A. max_so_far initialized to 0 causes wrong result for all negatives

B. Using elif instead of if causes skipping reset of max_ending_here

C. Loop should start from 1, not 0

D. max_ending_here should be initialized to float('-inf')

Solution

1. Step 1: Trace execution on [-3, -2, -1]

   max_so_far=0, max_ending_here=0.
   i=0, x=-3: meh=-3; 0 < -3? no; elif -3<0: yes, meh=0.
   i=1, x=-2: meh=-2; no update; reset meh=0.
   i=2, x=-1: meh=-1; no update; reset.
   Returns 0, but correct max subarray sum is -1.

2. Step 2: Why A and not others

   Init max_so_far=0 prevents update when all negative (meh never >0). B: elif ok here (if never true, always resets). C: range correct. D: meh=0 correct.

3. Final Answer:

   max_so_far initialized to 0 causes wrong result for all negatives -> Option A

4. Quick Check:

   Init max_so_far to float('-inf') for negatives [OK]

Hint: Initialize max_so_far to float('-inf') to handle all-negative arrays [OK]

Common Mistakes:

• Initializing max_so_far to 0 fails with all negatives
• Using elif causes reset to be skipped
• Wrong loop range causes index errors

5. Given an array of integers, how can Kadane's Algorithm be adapted to also return the start and end indices of the maximum sum subarray?
Choose the best approach.

hard

A. Use a nested loop to check all subarrays and record indices

B. Track current start index when resetting max_ending_here; update global start and end when max_so_far changes

C. Store all subarrays and pick the max sum after the loop ends

D. Return max_so_far only; indices cannot be found with Kadane's Algorithm

Solution

1. Step 1: Understand Kadane's Algorithm extension

   To find indices, track the start index of the current subarray when max_ending_here resets to 0. When max_so_far updates, record current start and end indices.

2. Step 2: Compare with other options

   Store all subarrays and pick the max sum after the loop ends is inefficient and not Kadane's approach. Use a nested loop to check all subarrays and record indices is brute force, not Kadane's. Return max_so_far only; indices cannot be found with Kadane's Algorithm is incorrect; indices can be found.

3. Final Answer:

   Track current start index when resetting max_ending_here; update global start and end when max_so_far changes -> Option B

4. Quick Check:

   Track start on reset, update indices on max update [OK]

Hint: Track start index on reset, update when max_so_far changes [OK]

Common Mistakes:

• Ignoring index tracking in Kadane's Algorithm
• Using brute force instead of Kadane's logic
• Assuming indices can't be found with Kadane's