Maximum Subarray Sum Problem

The Maximum Subarray Sum problem asks: given an array of integers (which may include negative numbers), find the contiguous subarray with the largest sum, and return that sum.

Brute Force Approach

Check every possible subarray and compute its sum, keeping track of the maximum found. This takes O(n²) time, which is too slow for large arrays.

Kadane's Algorithm (Optimal Approach)

Kadane's Algorithm solves this in a single pass by keeping a running sum. At each element, decide whether to extend the existing subarray or start a new one from the current element.

def max_subarray_sum(nums):
    current_sum = max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Output: 6

Complexity

Applications

• Stock price analysis — best time period for maximum profit trends.
• Signal processing to find the strongest continuous segment.
• A common building block for more advanced DP problems.