MediumArrayDivide and ConquerDynamic Programming

Maximum Subarray

2 approaches, code in every language

Given an integer array nums, find a contiguous run of one or more elements whose total is as large as possible, and return that maximum total. The chosen slice must be a single unbroken window of the array.

The values may be negative, so the answer is not always the sum of everything; sometimes a single element is the best you can do. Solve it here with a divide-and-conquer strategy that considers the best window fully inside the left half, fully inside the right half, and one that straddles the midpoint.

Example 1

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

Output: 6

The window [4, -1, 2, 1] sums to 6, the largest achievable total.

Example 2

Input: nums = [-3, -1, -2]

Output: -1

Every value is negative, so the best window is the single element -1.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Divide and Conquer

Split at the midpoint and combine the best left window, best right window, and best crossing window.

Loading animation…

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

1Call the solver on the full range [0, length - 1].
2When the range holds a single element, that element's value is the answer for it.
3Otherwise split at the midpoint and recursively solve the left and right halves.
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.
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

Time

O(n log n)

Space

O(log n)

Each of the log n levels does O(n) crossing work; space is the recursion depth.

Kadane's Scan

Track the best window ending at each index in a single left-to-right pass.

Loading animation…

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

1Initialise both the running sum and the overall best to the first element.
2For each later element, set the running sum to the larger of the element alone or the element added to the previous running sum.
3Update the overall best whenever the running sum exceeds it.
4Because a fresh window can start anywhere, negative-only inputs correctly yield the largest single value.
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

Time

O(n)

Space

O(1)

A single linear pass with two scalar accumulators; the optimal approach in practice.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Best Trading Day Run is our own problem on the technique behind Maximum Subarray: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free