Maximum Subarray Problem

When it comes to algorithmic problem solving, one of the most well-known and frequently asked questions is the Maximum Subarray Problem. 

It teaches core problem-solving concepts such as greedy logic and dynamic programming. 

I’ve worked on solving large-scale algorithmic problems both in production systems and interviews, and today, I’ll walk you through a clean and professional solution to this problem.

The goal is simple: Given an array of integers, find the contiguous subarray with the largest sum. This article begins with the brute-force approach to give context and then leads to the optimized, industry-standard solution: Kadane’s Algorithm.

Brute-Force Approach (Inefficient)

Let’s first try the naive solution, like a baby learning to crawl before walking.

How it works:
    • Try every possible subarray.
    • Calculate the sum of each.
    • Keep track of the biggest one.

from typing import List

def max_subarray_brute_force(nums: List[int]) -> int:
    max_sum = float('-inf')
    n = len(nums)
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    return max_sum

Why it's slow:

    • Time complexity is O(n^2).
    • On 1 million elements, it will timeout.

Optimized Solution: Kadane’s Algorithm

Now let’s walk and even run — Kadane’s Algorithm is the fastest known method for solving this problem efficiently.

How Kadane’s Works (Baby Language Edition):

    • We keep a running total of the best sum ending here.
    • If adding a number makes it worse, we start fresh.
    • We remember the best ever total we’ve seen.

from typing import List

def max_subarray(nums: List[int]) -> int:
    """
    Find the maximum subarray sum using Kadane's Algorithm.

    Args:
        nums (List[int]): A list of integers.

    Returns:
        int: The largest sum of any contiguous subarray.
    """
    max_sum = nums[0]  # Start with the first number
    current_sum = nums[0]  # Also keep track of the sum so far

    for i in range(1, len(nums)):
        # Either start fresh from current number or extend the previous sum
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

Why It’s Fast:

    • Time complexity is O(n).
    • Only one loop — great for large input sizes.

Sample Outputs

Here’s how it performs with real test cases:

print("Expected 6, Actual:", max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
print("Expected 10, Actual:", max_subarray([1]*10 + [-100]*5 + [1]*10))
print("Expected 10**9, Actual:", max_subarray([-1]*10**6 + [10**9]))
print("Expected 10**6, Actual:", max_subarray([1]*10**6))
print("Expected 999998, Actual:", max_subarray([(-1)**i * i for i in range(1, 10**6)]))

These cases show how the optimized version handles even millions of numbers efficiently.

What You Should Do Next

This problem isn’t just a classic — it’s a building block for understanding more complex algorithms. Here’s how you can take it further:

    • Practice implementing Kadane’s from scratch.
    • Try modifying it to return the actual subarray, not just the sum.
    • Explore 2D variations (e.g., maximum sum rectangle in a matrix).

If you’re preparing for technical interviews or optimizing backend analytics systems, mastering this pattern will give you a serious edge.

Keep solving problems that push you to think — and keep optimizing like a pro.