Maximum Subarray

How it works

We want the maximum sum of a contiguous subarray.

Using divide and conquer, we split the array into two halves and solve the problem recursively.
For any subarray [l .. r], the maximum subarray must be one of these three cases:

1. Entirely in the left half
2. Entirely in the right half
3. Crossing the middle (includes the middle element)

The first two cases are solved recursively.
The third case is handled by:

• taking the maximum sum extending left from the middle
• taking the maximum sum extending right from the middle
• adding both to the middle element

The recursive function represents:
“What is the maximum subarray sum within the range [l .. r]?”

Steps

1. Define a recursive function dfs(l, r):
   • If l > r, return negative infinity (invalid range).
2. Find the middle index m of the range [l .. r].
3. Compute the maximum subarray sum that crosses the middle:
   • Move left from m - 1 to l, keeping the maximum prefix sum
   • Move right from m + 1 to r, keeping the maximum prefix sum
   • Combine them with nums[m].
4. Recursively compute:
   • maximum subarray in the left half - dfs(l, m - 1)
   • maximum subarray in the right half - dfs(m + 1, r).
5. Return the maximum of:
   • left result
   • right result
   • crossing-middle result.
6. Start the recursion with the full range [0 .. n - 1].
7. Return the final result.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(log n)

Things to watch for

Initializing the Result to Zero

When all elements in the array are negative, the maximum subarray sum is the largest negative number, not zero. Initializing maxSum to 0 instead of nums[0] (or negative infinity) causes the algorithm to incorrectly return 0 for all-negative arrays. Always initialize with the first element or a sufficiently small value.

Resetting Current Sum at the Wrong Time

In Kadane's algorithm, you should reset curSum to zero when it becomes negative, not when it becomes less than the current element. The condition if (curSum < 0) curSum = 0 should come before adding the current element, not after. Placing this check incorrectly changes when subarrays restart and produces wrong results.

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(l, r):
            if l > r:
                return float("-inf")

            m = (l + r) >> 1
            leftSum = rightSum = curSum = 0
            for i in range(m - 1, l - 1, -1):
                curSum += nums[i]
                leftSum = max(leftSum, curSum)

            curSum = 0
            for i in range(m + 1, r + 1):
                curSum += nums[i]
                rightSum = max(rightSum, curSum)

            return (max(dfs(l, m - 1),
                        dfs(m + 1, r),
                        leftSum + nums[m] + rightSum))

        return dfs(0, len(nums) - 1)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return dfs(nums, 0, nums.size() - 1);
    }

private:
    int dfs(vector<int>& nums, int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        int m = (l + r) >> 1;
        int leftSum = 0, rightSum = 0, curSum = 0;
        for (int i = m - 1; i >= l; --i) {
            curSum += nums[i];
            leftSum = max(leftSum, curSum);
        }
        curSum = 0;
        for (int i = m + 1; i <= r; ++i) {
            curSum += nums[i];
            rightSum = max(rightSum, curSum);
        }
        return max(dfs(nums, l, m - 1),
                   max(dfs(nums, m + 1, r),
                       leftSum + nums[m] + rightSum));
    }
};