53. Maximum Subarray - Explanation

Description

Given an array of integers nums, find the subarray with the largest sum and return the sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [2,-3,4,-2,2,1,-1,4]

Output: 8

Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Example 2:

Input: nums = [-1]

Output: -1

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force approach would be to compute the sum of every subarray and return the maximum among them. This would be an O(n^2) approach. Can you think of a better way? Maybe you should consider a dynamic programming-based approach.

Hint 2

Instead of calculating the sum for every subarray, try maintaining a running sum. Maybe you should consider whether extending the previous sum or starting fresh with the current element gives a better result. Can you think of a way to track this efficiently?

Hint 3

We use a variable curSum to track the sum of the elements. At each index, we have two choices: either add the current element to curSum or start a new subarray by resetting curSum to the current element. Maybe you should track the maximum sum at each step and update the global maximum accordingly.

Hint 4

This algorithm is known as Kadane's algorithm.

Company Tags

1. Brute Force

Intuition

This problem asks us to find the maximum sum of any contiguous subarray.

The most straightforward way to think about this is:

try every possible subarray
calculate its sum
keep track of the maximum sum we see

A subarray is defined by a start index i and an end index j.
By fixing i and expanding j to the right, we can compute the sum of all subarrays that start at i.

This approach is easy to understand and works well for learning, but it is not efficient for large inputs.

Algorithm

Let n be the length of the array.
Initialize the result res with the first element of the array.
Iterate over all possible starting indices i from 0 to n - 1:
For each starting index i:
- Initialize a running sum cur = 0
- Iterate over ending indices j from i to n - 1:
  - Add nums[j] to cur
  - Update res with the maximum of res and cur
After all subarrays are checked, return res.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                res = max(res, cur)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Recursion

Intuition

We want the maximum sum of a contiguous subarray.

Using recursion, we can think of the problem as making a decision at each index:

either we haven’t started a subarray yet
or we are already inside a subarray and can choose whether to continue it or stop

The recursive function keeps track of this using a flag:

flag = False - we have not started a subarray yet
flag = True - we are currently building a subarray

The function answers the question:
“What is the maximum subarray sum we can get starting from index i, given whether we are already inside a subarray or not?”

By exploring both possibilities at every step, the recursion eventually finds the best contiguous subarray.

Algorithm

Define a recursive function dfs(i, flag):
- i is the current index in the array
- flag indicates whether a subarray has already started
Base case:
- If i reaches the end of the array:
  - Return 0 if a subarray was already started
  - Otherwise return a very small value (to ensure at least one element is chosen)
If flag is True (we are inside a subarray):
- We have two choices:
  - stop the subarray - return 0
  - continue the subarray - add nums[i] and recurse
- Take the maximum of these two options
If flag is False (we have not started yet):
- We can either:
  - skip the current element and stay outside the subarray
  - start a new subarray at the current element
- Take the maximum of these two choices
Start the recursion with dfs(0, False)
Return the final result.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(i, flag):
            if i == len(nums):
                return 0 if flag else -1e6
            if flag:
                return max(0, nums[i] + dfs(i + 1, True))
            return max(dfs(i + 1, False), nums[i] + dfs(i + 1, True))
        return dfs(0, False)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

3. Dynamic Programming (Top-Down)

Intuition

We want to find the maximum sum of a contiguous subarray.

In the recursive solution, we modeled the problem using two states:

we have not started a subarray yet
we are already inside a subarray

However, plain recursion repeats the same computations many times.
To optimize this, we use top-down dynamic programming (memoization).

Each state is uniquely identified by:

i: the current index in the array
flag: whether a subarray has already started (True) or not (False).

The function answers:
“What is the maximum subarray sum we can get starting from index i, given whether a subarray is already in progress?”

By storing results for each (i, flag) state, we avoid recomputing them.

Algorithm

Create a memo table memo where:
- memo[i][flag] stores the maximum subarray sum starting at index i
  given whether a subarray has started.
Define a recursive function dfs(i, flag):
- i is the current index
- flag indicates whether a subarray is already in progress.
Base case:
- If i reaches the end of the array:
  - Return 0 if a subarray was started
  - Otherwise return a very small value (to force choosing at least one element).
If the result for (i, flag) is already stored in memo:
- Return it directly.
If flag is True (inside a subarray):
- Either stop the subarray (0)
- Or continue it by adding nums[i]
- Store the maximum of these two options.
If flag is False (not started yet):
- Either skip the current element
- Or start a new subarray at the current element
- Store the maximum of these two choices.
Start the recursion with dfs(0, False).
Return the final result.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        memo = [[None] * 2 for _ in range(len(nums) + 1)]

        def dfs(i, flag):
            if i == len(nums):
                return 0 if flag else -1e6
            if memo[i][flag] is not None:
                return memo[i][flag]
            if flag:
                memo[i][flag] = max(0, nums[i] + dfs(i + 1, True))
            else:
                memo[i][flag] = max(dfs(i + 1, False),
                                    nums[i] + dfs(i + 1, True))
            return memo[i][flag]

        return dfs(0, False)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up)

Intuition

We want the maximum sum of a contiguous subarray.

From the recursive and top-down DP solutions, we observed two useful states:

the best subarray sum starting exactly at index i
the best subarray sum starting at or after index i

Instead of recursion, we can compute these values iteratively using bottom-up dynamic programming.

At each index, we decide:

whether to start a new subarray at the current element
or extend a subarray from the next index

By filling the DP table from right to left, all needed future values are already known.

Algorithm

Let n be the length of the array.
Create a DP table dp of size n x 2:
- dp[i][1] = maximum subarray sum that must start at index i
- dp[i][0] = maximum subarray sum that starts at index i or later
Initialize the base case at the last index:
- dp[n - 1][1] = nums[n - 1]
- dp[n - 1][0] = nums[n - 1]
Iterate i from n - 2 down to 0:
- Compute dp[i][1]:
  - either start a new subarray at i - nums[i]
  - or extend the subarray from i + 1 - nums[i] + dp[i + 1][1]
- Compute dp[i][0]:
  - either the best subarray starts later - dp[i + 1][0]
  - or it starts exactly at i - dp[i][1]
After filling the table, dp[0][0] contains the maximum subarray sum.
Return dp[0][0].

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * 2 for _ in range(n)]
        dp[n - 1][1] = dp[n - 1][0] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            dp[i][1] = max(nums[i], nums[i] + dp[i + 1][1])
            dp[i][0] = max(dp[i + 1][0], dp[i][1])

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Dynamic Programming (Space Optimized)

Intuition

We want the maximum sum of a contiguous subarray.

At every position, we have a simple choice:

start a new subarray at the current element
or extend the subarray that ended at the previous index

If the sum up to the previous index is negative, extending it would only make things worse, so we start fresh at the current element.

This idea allows us to keep track of the best subarray sum ending at each index and update it in a single pass.

Algorithm

Create an array dp where:
- dp[i] represents the maximum subarray sum ending at index i.
Initialize dp as a copy of nums since the smallest subarray ending at each index is the element itself.
Iterate through the array from index 1 to the end:
- Update dp[i] as:
  - the maximum of starting fresh at nums[i]
  - or extending the previous subarray: nums[i] + dp[i - 1].
The maximum subarray sum is the maximum value in dp.
Return that value.

class Solution:
    def maxSubArray(self, nums):
        dp = [*nums]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i - 1])
        return max(dp)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

6. Kadane's Algorithm

Intuition

We want the maximum sum of a contiguous subarray.

Kadane’s Algorithm is based on one simple observation:

if the running sum becomes negative, keeping it will only reduce the sum of any future subarray

So whenever the current sum drops below zero, we reset it and start a new subarray from the next element.

As we scan the array once, we keep track of:

the best subarray sum ending at the current position
the best subarray sum seen overall

Algorithm

Initialize:
- curSum = 0 to track the running subarray sum
- maxSub as the first element (handles all-negative arrays).
Iterate through each number in the array:
If curSum becomes negative:
- reset it to 0 (start a new subarray).
Add the current number to curSum.
Update maxSub with the maximum of maxSub and curSum.
After processing all elements, return maxSub.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub, curSum = nums[0], 0
        for num in nums:
            if curSum < 0:
                curSum = 0
            curSum += num
            maxSub = max(maxSub, curSum)
        return maxSub

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

7. Divide & Conquer

Intuition

We want the maximum sum of a contiguous subarray.

Using divide and conquer, we split the array into two halves and solve the problem recursively.
For any subarray [l .. r], the maximum subarray must be one of these three cases:

Entirely in the left half
Entirely in the right half
Crossing the middle (includes the middle element)

The first two cases are solved recursively.
The third case is handled by:

taking the maximum sum extending left from the middle
taking the maximum sum extending right from the middle
adding both to the middle element

The recursive function represents:
“What is the maximum subarray sum within the range [l .. r]?”

Algorithm

Define a recursive function dfs(l, r):
- If l > r, return negative infinity (invalid range).
Find the middle index m of the range [l .. r].
Compute the maximum subarray sum that crosses the middle:
- Move left from m - 1 to l, keeping the maximum prefix sum
- Move right from m + 1 to r, keeping the maximum prefix sum
- Combine them with nums[m].
Recursively compute:
- maximum subarray in the left half - dfs(l, m - 1)
- maximum subarray in the right half - dfs(m + 1, r).
Return the maximum of:
- left result
- right result
- crossing-middle result.
Start the recursion with the full range [0 .. n - 1].
Return the final result.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(l, r):
            if l > r:
                return float("-inf")

            m = (l + r) >> 1
            leftSum = rightSum = curSum = 0
            for i in range(m - 1, l - 1, -1):
                curSum += nums[i]
                leftSum = max(leftSum, curSum)

            curSum = 0
            for i in range(m + 1, r + 1):
                curSum += nums[i]
                rightSum = max(rightSum, curSum)

            return (max(dfs(l, m - 1),
                        dfs(m + 1, r),
                        leftSum + nums[m] + rightSum))

        return dfs(0, len(nums) - 1)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(\log n)$

Common Pitfalls

Initializing the Result to Zero

When all elements in the array are negative, the maximum subarray sum is the largest negative number, not zero. Initializing maxSum to 0 instead of nums[0] (or negative infinity) causes the algorithm to incorrectly return 0 for all-negative arrays. Always initialize with the first element or a sufficiently small value.

Resetting Current Sum at the Wrong Time

In Kadane's algorithm, you should reset curSum to zero when it becomes negative, not when it becomes less than the current element. The condition if (curSum < 0) curSum = 0 should come before adding the current element, not after. Placing this check incorrectly changes when subarrays restart and produces wrong results.