53. Maximum Subarray

Problem¶

Given a non-empty integer array nums, return the largest possible sum of any contiguous subarray.

Example:

nums = [-2,1,-3,4,-1,2,1,-5,4] -> 6
best subarray: [4,-1,2,1]

Key trick¶

Use Kadane's algorithm:

Keep the best sum ending at the current index.
Either extend the previous subarray or start fresh at the current number.
Track the global maximum.

Trap¶

Common mistakes:

Returning 0 for all-negative arrays.
Resetting too early and losing the case where the best subarray is a single negative number.
Confusing contiguous subarray with subsequence.

Why is it interesting?¶

It is a simple-looking problem that tests whether you can:

Turn a brute force idea into a linear-time DP/greedy solution.
Maintain the right invariant with only \(O(1)\) extra space.

Python solution¶

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        cur = nums[0] # best sum of a subarray ending at current position
        best = nums[0] # best sum seen anywhere

        for x in nums[1:]:
            # either extend previous subarray or start at x
            cur = max(x, cur + x)
            best = max(best, cur)

        return best

Comment on my solution¶

Your solution is correct and linear.

Small improvements:

Use the standard Kadane form cur = max(x, cur + x).
It is simpler than storing cur_sum as max(sum, 0).
Your comments are a bit long for an interview; shorter invariants are easier to explain.

import pytest

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best_sum = nums[0] # up to i - 1 (here i = 1)
        # subarray up to i - 1 with largest sum
        # we restart the array when adding it nums[i] go
        cur_sum = max(nums[0], 0)
        for n in nums[1:]:
            new_sum = cur_sum + n
            if best_sum < new_sum:
                best_sum = new_sum
            # if new_sum < 0, we want to start a new subarray on the next
            # number in nums.  So we reset cur_sum to 0.
            # if not, we continue summing on the current subarray
            cur_sum = max(new_sum, 0)

        return best_sum

@pytest.mark.parametrize(
    ("nums", "expected_max"),
    [
        ([-2,1,-3,4,-1,2,1,-5,4], 6), # [4,-1,2,1]
        ([1], 1),
        ([5,4,-1,7,8], 23) # [5,4,-1,7,8]
    ]
)
def test_maxSubArray(nums, expected_max):
    assert Solution().maxSubArray(nums) == expected_max

A cleaner version of your idea:

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        cur = best = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)
            best = max(best, cur)
        return best