Maximum Subarray

Intuition

Any maximum-sum window either lives entirely in the left half, entirely in the right half, or spans the boundary between them. The first two cases are solved by recursion on each half. The crossing case is special: it must include the midpoint, so we extend greedily leftward from the middle to find the largest suffix sum of the left half, extend rightward for the largest prefix sum of the right half, and add them. Taking the maximum of the three candidates at every level yields the overall answer.

Algorithm walkthrough

1. 1Call the solver on the full range [0, length - 1].
2. 2When the range holds a single element, that element's value is the answer for it.
3. 3Otherwise split at the midpoint and recursively solve the left and right halves.
4. 4Compute the best crossing sum by walking left from mid for the largest suffix and right from mid + 1 for the largest prefix, then adding them.
5. 5Return the maximum among the left result, the right result, and the crossing result.

Implementation

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        return self._solve(nums, 0, len(nums) - 1)

    def _solve(self, nums: List[int], lo: int, hi: int) -> int:
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        left = self._solve(nums, lo, mid)
        right = self._solve(nums, mid + 1, hi)
        cross = self._cross_sum(nums, lo, mid, hi)
        return max(left, right, cross)

    def _cross_sum(self, nums: List[int], lo: int, mid: int, hi: int) -> int:
        left_best = float("-inf")
        total = 0
        for i in range(mid, lo - 1, -1):
            total += nums[i]
            left_best = max(left_best, total)
        right_best = float("-inf")
        total = 0
        for i in range(mid + 1, hi + 1):
            total += nums[i]
            right_best = max(right_best, total)
        return left_best + right_best

Intuition

The divide-and-conquer view is instructive, but this problem also has a clean linear solution. Scanning once, keep a running sum of the best window that ends exactly at the current index: extending the previous window only helps if that previous sum was positive, otherwise it is better to restart from the current element. The largest running value seen across the whole scan is the answer. This is the standard optimal approach and is worth knowing alongside the divide-and-conquer method.

Algorithm walkthrough

1. 1Initialise both the running sum and the overall best to the first element.
2. 2For each later element, set the running sum to the larger of the element alone or the element added to the previous running sum.
3. 3Update the overall best whenever the running sum exceeds it.
4. 4Because a fresh window can start anywhere, negative-only inputs correctly yield the largest single value.
5. 5After one pass, the overall best holds the maximum subarray sum.

Implementation

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = current = nums[0]
        for i in range(1, len(nums)):
            current = max(nums[i], current + nums[i])
            best = max(best, current)
        return best