LeetCode 53: Maximum Subarray

Problem Restatement

We are given an integer array nums.

We need to find the contiguous subarray with the largest possible sum and return that sum.

A subarray means a continuous part of the array. We cannot skip elements.

The official problem asks for the largest subarray sum, not the subarray itself. The constraints are 1 <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4.

Input and Output

Function shape:

def maxSubArray(nums: list[int]) -> int:
    ...

Examples

For:

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

The best subarray is:

[4, -1, 2, 1]

Its sum is:

4 + (-1) + 2 + 1 = 6

So the answer is:

6

For:

nums = [1]

The only non-empty subarray is [1], so the answer is:

1

For:

nums = [5,4,-1,7,8]

The best subarray is the entire array:

[5, 4, -1, 7, 8]

The answer is:

23

First Thought: Brute Force

The simplest approach is to try every possible subarray.

Choose a start index i.

Then extend the subarray to every end index j.

While extending, keep a running sum.

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best = nums[0]
        n = len(nums)

        for i in range(n):
            total = 0

            for j in range(i, n):
                total += nums[j]
                best = max(best, total)

        return best

This checks all contiguous subarrays and records the largest sum.

Problem With Brute Force

There are many subarrays.

For an array of length n, the number of possible start and end pairs is about n^2.

So this solution takes:

O(n^2)

The constraint allows up to 10^5 elements, so quadratic time is too slow.

We need a linear solution.

Key Insight

At each index, ask one question:

Should the best subarray ending here extend the previous subarray, or should it start fresh here?

For a number num, there are only two choices:

current + num

or:

num

If the previous running sum helps us, we keep it.

If the previous running sum hurts us, we discard it and start a new subarray at the current number.

This gives the recurrence:

current = max(num, current + num)

Then the global answer is the largest current value seen so far.

This is Kadane’s algorithm.

Algorithm

Initialize:

current = nums[0]
best = nums[0]

Then scan from the second element onward.

For each num:

1. Update current to the best subarray sum ending at this element.
2. Update best to the best subarray sum seen anywhere so far.

current = max(num, current + num)
best = max(best, current)

At the end, return best.

Correctness

Let current mean the maximum sum of a non-empty subarray that must end at the current index.

For the current number num, any subarray ending here has only two forms.

It either starts at the current index, giving sum num, or it extends a subarray ending at the previous index, giving sum current + num.

Taking the maximum of those two choices gives the best subarray ending at the current index.

The variable best stores the largest value of current seen so far. Since every non-empty subarray ends at some index, checking the best ending value at every index guarantees that best becomes the maximum subarray sum over the whole array.

Complexity

Implementation

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        current = nums[0]
        best = nums[0]

        for num in nums[1:]:
            current = max(num, current + num)
            best = max(best, current)

        return best

Code Explanation

We initialize both values with the first element:

current = nums[0]
best = nums[0]

This matters because the array may contain only negative numbers.

For example:

nums = [-3, -2, -5]

The answer should be -2, not 0.

Then we process the rest of the array:

for num in nums[1:]:

At each number, we decide whether to extend the previous subarray or start a new one:

current = max(num, current + num)

Then we update the global answer:

best = max(best, current)

Finally, return:

return best

Testing

def run_tests():
    s = Solution()

    assert s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6
    assert s.maxSubArray([1]) == 1
    assert s.maxSubArray([5,4,-1,7,8]) == 23
    assert s.maxSubArray([-3, -2, -5]) == -2
    assert s.maxSubArray([0, 0, 0]) == 0
    assert s.maxSubArray([-1, 2, 3, -10, 4]) == 5

    print("all tests passed")

run_tests()