Maximum Subarray Sum(Kadane’s Algorithm) in Python

📋 Problem Statement

Given an array of integers (which can include negatives), find the contiguous subarray with the largest subarrays sum and return that sum.

Example 1

Example 2

📥 Input / Output Format & Constraints

🐢 Naive Approach (Brute Force)

The simplest idea: try every possible subarray, compute its subarrays sum, track the maximum. Two common brute-force versions exist:

• O(n³) approach — Three nested loops: pick start, pick end, loop to sum
• O(n²) approach — Two loops: pick start, extend end while accumulating subarrays sum

# O(n²) brute force — computes subarrays sum for every pair
def max_subarray_brute(arr):
    n = len(arr)
    max_sum = arr[0]
    for i in range(n):
        curr = 0
        for j in range(i, n):
            curr += arr[j]          
            max_sum = max(max_sum, curr)
    return max_sum

⚡ Optimal Approach – Kadane’s Algorithm

Kadane’s Algorithm computes the maximum subarrays sum in a single pass using one brilliant observation:

Only 2 variables are needed:

• current_sum — the best subarrays sum ending at the current index
• max_sum — the best subarrays sum seen anywhere in the array so far

At each step: current_sum = max(arr[i], current_sum + arr[i]). If the running subarrays sum is less than starting fresh, we restart. Then update max_sum if needed.

🔀 Algorithm Flowchart

📝 Pseudocode

FUNCTION kadane(arr):
    // Initialize both values to arr[0] for all-negative support
    current_sum ← arr[0]
    max_sum     ← arr[0]      // tracks best subarrays sum so far

    FOR i FROM 1 TO length(arr) - 1:
        current_sum ← MAX(arr[i], current_sum + arr[i])
        max_sum     ← MAX(max_sum, current_sum)

    RETURN max_sum             // maximum subarrays sum

🐍 Python Program

def kadane(arr):
    # Initialize to arr[0] — handles all-negative arrays correctly
    current_sum = arr[0]
    max_sum     = arr[0]   # best subarrays sum found so far

    for i in range(1, len(arr)):
        # Extend current subarray OR start a new one from arr[i]
        current_sum = max(arr[i], current_sum + arr[i])

        # Update maximum subarrays sum if we found a better one
        max_sum = max(max_sum, current_sum)

    return max_sum   # final answer: maximum subarrays sum


n   = int(input("Enter size of array: "))
arr = list(map(int, input("Enter elements: ").split()))

result = kadane(arr)
print("Maximum Subarrays Sum:", result)

🔍 Dry Run — Step by Step

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

Initial: current_sum = –2, max_sum = –2 (subarrays sum starts at first element)

💡 Code Explanation

• current_sum = arr[0] — Start at the first element. Initializing to 0 would break all-negative subarrays sum cases.
• max_sum = arr[0] — Tracks the overall best subarrays sum across the entire array.
• max(arr[i], current_sum + arr[i]) — The core of Kadane’s: restart vs extend. If the current subarrays sum running total is dragging you down, cut it.
• max(max_sum, current_sum) — After each step, update the global maximum subarrays sum if needed.
• return max_sum — The final maximum subarrays sum after processing all elements.

📊 Time & Space Complexity

🧪 Test Cases

⚠️ Edge Cases to Watch

• All negatives: Don’t initialize max_sum to 0 — the subarrays sum answer would be wrong. Start with arr[0].
• Single element: The loop never runs; subarrays sum = arr[0]. Works correctly.
• Array with only zeros: Maximum subarrays sum = 0. The algorithm handles it cleanly.
• Very large values: Python handles arbitrarily large integers — no overflow when computing subarrays sum.

🧠 Why Kadane’s Algorithm Works

Think of the subarrays sum like a stock portfolio. Each array element is a daily gain or loss. If your running total (subarrays sum so far) is negative, carrying it forward can only hurt you — so you cut losses and restart fresh.

Formally, Kadane’s computes the maximum subarrays sum ending at each index using this DP recurrence:

🎯 Common Interview Questions on Subarrays Sum

🌍 Real World Applications of Subarrays Sum

🚫 Mistakes Beginners Make with Subarrays Sum

🏁 Conclusion

Kadane’s Algorithm is the definitive solution for the maximum subarrays sum problem. It’s elegant, fast, and once you understand the core insight — if the subarrays sum so far hurts you, let it go — you’ll never forget it.

This problem appears constantly in technical interviews, and explaining it confidently with a dry run, complexity analysis, and edge cases puts you miles ahead of other candidates.

Want to level up further? Try these related subarrays sum challenges:

• Return the actual subarray that gives the maximum subarrays sum
• Maximum subarray product (a twist on the subarrays sum idea)
• Maximum circular subarrays sum

❓ Frequently Asked Questions – Subarrays Sum & Kadane’s Algorithm

🎯 Featured Snippet – Quick Answer