53. Maximum Subarray

Reformulated question¶

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 this question is 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.

Solve the problem with idiomatic python¶

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

        # best sum seen anywhere
        best = nums[0]

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

        return best

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),
        ([1], 1),
        ([5, 4, -1, 7, 8], 23),
        ([-1], -1),
        ([-5, -2, -7], -2),
        ([0, 0, 0], 0),
        ([8, -19, 5, -4, 20], 21),
        ([1, -1, 1, -1, 1], 1),
    ],
)
def test_max_sub_array(nums, expected):
    assert Solution().maxSubArray(nums) == expected

Comment 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