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.