LeetCode Problem 53

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Dynamic Programming

Solution

LeetCode 53, Maximum Subarray

Problem Understanding

The problem gives an integer array nums and asks us to find a contiguous subarray that has the largest possible sum. A subarray means the elements must appear next to each other in the original array. We are not allowed to rearrange elements or skip positions arbitrarily.

The output is not the subarray itself, but the maximum sum that any contiguous subarray can produce.

For example, in the array:

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

the best contiguous segment is:

[4,-1,2,1]

Its sum is:

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

so the answer is 6.

The constraints are important:

• The array length can be as large as 10^5
• Values can be positive, negative, or zero

Because the input can contain one hundred thousand elements, any algorithm slower than linear or near linear time becomes impractical. A quadratic solution would perform around 10^10 operations in the worst case, which is far too slow.

An important detail is that the array always contains at least one element. This means we never need to handle an empty array.

Several edge cases are especially important:

• Arrays containing only negative numbers
• Arrays containing only positive numbers
• Arrays with a single element
• Arrays where the optimal subarray appears in the middle
• Arrays where restarting the subarray is better than extending it

A naive implementation often fails on all negative arrays because it incorrectly assumes the answer should never be negative. However, if every number is negative, the correct answer is the least negative single element.

Approaches

Brute Force Approach

The brute force method considers every possible contiguous subarray and computes its sum.

For an array of length n, there are:

n * (n + 1) / 2

possible subarrays.

We can generate every starting index and every ending index, then compute the sum of the elements between them. While doing this, we keep track of the maximum sum seen so far.

This approach is correct because it exhaustively checks every possible contiguous subarray. Since the optimal answer must be one of those subarrays, the algorithm is guaranteed to find it.

However, this approach is too slow for the given constraints. Even with prefix sum optimization, checking all subarrays requires O(n^2) time, which is not feasible for n = 10^5.

Optimal Approach, Kadane's Algorithm

The key observation is that when building a subarray, a negative running sum is harmful.

Suppose we are currently processing an element nums[i].

We have two choices:

1. Extend the previous subarray
2. Start a new subarray at the current element

If the previous running sum is negative, extending it only makes the current total worse. In that case, it is always better to discard the previous subarray and start fresh from the current element.

This insight leads to Kadane's Algorithm.

At each position, we compute:

• The maximum subarray sum ending at the current index
• The best global maximum seen so far

This allows us to solve the problem in a single pass through the array.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal, Kadane's Algorithm	O(n)	O(1)	Uses running maximum subarray sums

Algorithm Walkthrough

Kadane's Algorithm

1. Initialize two variables using the first element of the array.

current_sum represents the maximum subarray sum ending at the current position.

max_sum represents the best subarray sum found anywhere so far.

We initialize both to nums[0] because the array is guaranteed to contain at least one element. 2. Iterate through the array starting from index 1.

For each element, decide whether it is better to:

• Start a new subarray using only the current element
• Extend the previous subarray

3. Update current_sum.

The recurrence relation is:

$\text{current_sum} = \max(\text{nums}[i],\ \text{current_sum} + \text{nums}[i])$

This means:

• If the previous running sum is harmful, restart
• Otherwise, extend the existing subarray

4. Update max_sum.

After computing the best subarray ending at the current index, compare it with the global best answer seen so far.

$\text{max_sum} = \max(\text{max_sum},\ \text{current_sum})$ 5. Continue until the entire array has been processed. 6. Return max_sum.

Why It Works

The algorithm maintains an important invariant:

• current_sum always stores the maximum possible subarray sum ending at the current index.
• max_sum always stores the maximum subarray sum seen anywhere in the array so far.

At every step, the algorithm makes the locally optimal choice between restarting or extending. Because any negative prefix can only reduce future sums, discarding it is always safe. This guarantees that the algorithm never misses the globally optimal subarray.

Python Solution

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = nums[0]
        max_sum = nums[0]

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

        return max_sum

The implementation begins by initializing both current_sum and max_sum to the first element. This is important because the array may contain only negative numbers, so initializing to 0 would produce incorrect results.

The loop starts from index 1 because the first element has already been used for initialization.

Inside the loop, the algorithm decides whether to continue the existing subarray or begin a new one at the current element. This logic is implemented with:

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

The global answer is then updated using:

max_sum = max(max_sum, current_sum)

After processing all elements, max_sum contains the largest subarray sum.

Go Solution

func maxSubArray(nums []int) int {
    currentSum := nums[0]
    maxSum := nums[0]

    for i := 1; i < len(nums); i++ {
        if currentSum+nums[i] > nums[i] {
            currentSum = currentSum + nums[i]
        } else {
            currentSum = nums[i]
        }

        if currentSum > maxSum {
            maxSum = currentSum
        }
    }

    return maxSum
}

The Go implementation follows the same logic as the Python solution.

Go does not provide a built in max function for integers, so explicit conditional statements are used instead.

The problem guarantees at least one element, so accessing nums[0] is safe.

Since the constraints are relatively small, standard Go int values are sufficient and there is no risk of integer overflow.

Worked Examples

Example 1

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

Initial state:

current_sum = -2
max_sum = -2

Index	Value	current_sum Calculation	current_sum	max_sum
0	-2	Initial value	-2	-2
1	1	max(1, -2 + 1)	1	1
2	-3	max(-3, 1 + -3)	-2	1
3	4	max(4, -2 + 4)	4	4
4	-1	max(-1, 4 + -1)	3	4
5	2	max(2, 3 + 2)	5	5
6	1	max(1, 5 + 1)	6	6
7	-5	max(-5, 6 + -5)	1	6
8	4	max(4, 1 + 4)	5	6

Final answer:

6

The optimal subarray is:

[4,-1,2,1]

Example 2

nums = [1]

Initial state:

current_sum = 1
max_sum = 1

No loop iterations occur because the array has only one element.

Final answer:

1

Example 3

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

Initial state:

current_sum = 5
max_sum = 5

Index	Value	current_sum Calculation	current_sum	max_sum
0	5	Initial value	5	5
1	4	max(4, 5 + 4)	9	9
2	-1	max(-1, 9 + -1)	8	9
3	7	max(7, 8 + 7)	15	15
4	8	max(8, 15 + 8)	23	23

Final answer:

23

The entire array forms the optimal subarray.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan through the array. Each iteration performs only constant time operations.

No auxiliary data structures are required, so the extra memory usage remains constant regardless of input size.

Test Cases

sol = Solution()

assert sol.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6
# Standard mixed positive and negative case

assert sol.maxSubArray([1]) == 1
# Single positive element

assert sol.maxSubArray([-1]) == -1
# Single negative element

assert sol.maxSubArray([5,4,-1,7,8]) == 23
# Entire array is optimal

assert sol.maxSubArray([-2,-3,-1,-5]) == -1
# All negative numbers

assert sol.maxSubArray([1,2,3,4]) == 10
# All positive numbers

assert sol.maxSubArray([0,0,0]) == 0
# All zeros

assert sol.maxSubArray([-2,1]) == 1
# Restarting after negative prefix

assert sol.maxSubArray([8,-19,5,-4,20]) == 21
# Optimal subarray appears later

assert sol.maxSubArray([100000]) == 100000
# Large positive value

assert sol.maxSubArray([-10000]) == -10000
# Minimum constraint value

assert sol.maxSubArray([3,-2,5,-1]) == 6
# Best subarray spans multiple segments

Test Case Summary

Test	Why
[-2,1,-3,4,-1,2,1,-5,4]	Standard mixed input
[1]	Single positive element
[-1]	Single negative element
[5,4,-1,7,8]	Entire array is optimal
[-2,-3,-1,-5]	All negative values
[1,2,3,4]	All positive values
[0,0,0]	All zeros
[-2,1]	Requires restarting subarray
[8,-19,5,-4,20]	Optimal subarray appears later
[100000]	Large positive boundary value
[-10000]	Large negative boundary value
[3,-2,5,-1]	Mixed transitions between extend and restart

Edge Cases

All Numbers Are Negative

An all negative array is one of the most common sources of bugs. A naive implementation may initialize the answer to 0, which would incorrectly suggest that choosing no elements is allowed.

For example:

[-3,-2,-5]

The correct answer is -2, not 0.

The implementation handles this correctly by initializing both current_sum and max_sum to the first array element instead of zero.

Single Element Array

The smallest valid input contains exactly one number.

For example:

[7]

The algorithm should immediately return 7.

Because initialization uses the first element and the loop starts at index 1, the implementation naturally handles this case without special logic.

Large Negative Prefix

Sometimes the beginning of the array contains values that would reduce future sums.

For example:

[-100, 5, 6]

Extending the prefix produces:

-89

which is worse than starting fresh at 5.

Kadane's Algorithm correctly discards harmful prefixes using:

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

This ensures the algorithm always keeps the best possible subarray ending at the current position.