LeetCode 53 - Maximum Subarray

This Medium problem asks for the largest sum among all non-empty contiguous subarrays. I spent a while trying to avoid recalculating every possible range, but I did not reach a linear-time solution until I checked a hint and worked through Kadane’s algorithm. I had apparently solved it before. None of it came back to me.

Problem link and explanation

Problem: 53. Maximum Subarray
Summary: Given an integer array, return the largest sum of any contiguous subarray containing at least one element.

Consider this input:

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

The maximum-sum range is [4, -1, 2, 1], which produces 6. The values must remain contiguous; this is not a problem where arbitrary elements can be selected and combined.

Checking every start and end position works, but it produces O(n²) ranges. Kadane’s algorithm reduces the work to one pass by keeping only the maximum sum of a subarray ending at the current position.

Approach

Decide whether to extend or restart

At index i, the best subarray ending at that position has two possible sources:

extend the previous subarray with nums[i]
start a new subarray at nums[i]

If prev_sum stores the maximum sum ending at the previous index, the next value is:

prev_sum = max(prev_sum + nums[i], nums[i])

The decision comes from directly comparing prev_sum + nums[i] with nums[i]. If the first value is larger, the previous range is worth extending. If the second is larger, the previous range is discarded and a new one starts at the current number.

After this assignment, prev_sum is the maximum sum of a contiguous subarray that must end at index i.

Track the global maximum separately

The best range may have ended at an earlier index, so max_sum records the largest prev_sum seen during the scan.

max_sum = max(max_sum, prev_sum)

Part of the sample progresses as follows:

current     prev_sum     max_sum
   -2           -2          -2
    1            1           1
   -3           -2           1
    4            4           4
   -1            3           4
    2            5           5
    1            6           6

The sum ending at -3 does not improve the next value, so the algorithm starts again at 4. The following -1 lowers the running sum, but keeping it preserves the contiguous range that later reaches 6 after adding 2 and 1.

Troubleshooting

I initially tried to reason about both boundaries of each contiguous range. That leads back toward comparing many possible start and end positions, even though the problem asks only for the sum and does not require the indices.

Kadane’s algorithm reduces that range decision to one state: the best sum ending at the current position. Each step decides whether to extend the previous range or restart at the current value, while a second variable retains the best result found anywhere in the array.

The initialization also matters.

prev_sum = nums[0]
max_sum = nums[0]

For an all-negative input such as [-3, -2, -5], the correct answer is -2. Initializing max_sum to zero would incorrectly allow an empty subarray that the problem does not permit. Starting both variables with the first element handles negative-only arrays and lets the loop begin at the second element.

Complexity analysis

Time complexity: O(n)
- The algorithm visits each array element once and performs constant-time addition and comparison at every step.
Space complexity: O(1)
- It keeps only a few scalar variables regardless of the input size.

Implementation code

from typing import List

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

        prev_sum = nums[0]
        max_sum = prev_sum

        for i in range(1, n):
            prev_sum = max(prev_sum + nums[i], nums[i])
            max_sum = max(max_sum, prev_sum)

        return max_sum

Summary and reflection

The exact meaning of prev_sum is the maximum sum of a contiguous subarray ending at the current index. That definition turns the range decision into one comparison between extending the previous result and starting again with the current number. max_sum then preserves the best value across all ending positions.

There is no need to construct every range because each step depends only on the state produced at the previous position. Defining the state needed by the next iteration was the part that converted the nested range search into a linear scan.