← All problems
🧠 Recursive Visual Explanation

Maximum Subarray Recursion Visualizer

Understand the recursive state, choices, base case, and how the same recurrence becomes Kadane's Algorithm.

Question

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, which is 8.
Example 2

Input: nums = [-1]
Output: -1

Constraints

  • 1 ≤ nums.length ≤ 100,000
  • -10,000 ≤ nums[i] ≤ 10,000

1. The recursive state

Define:

solve(i) = maximum subarray sum
that must end at index i

This definition is powerful because if the subarray must end at index i, then nums[i] must be included.

2. The two choices

At index i, there are only two meaningful possibilities:

1. Start a new subarray at i
   → nums[i]

2. Extend the best subarray ending at i - 1
   → nums[i] + solve(i - 1)
We do not use a normal “take or skip” recurrence because a subarray must remain contiguous.

3. The recurrence

solve(i) = max(
  nums[i],
  nums[i] + solve(i - 1)
)

If the previous sum is harmful, start fresh. If it helps, extend it.

4. Interactive animation

Use the example [2, -3, 4, -2, 2, 1, -1, 4]. Click “Next step” to see the recurrence evaluate each index.

Choice A — Start New

Start a new subarray using only nums[i].

—

Choice B — Extend Previous

Continue the best subarray that ended at i - 1.

—
Click “Next step” to begin.

5. Base case

if i == 0:
  return nums[0]

The only non-empty subarray that ends at index 0 is:

[nums[0]]

So solve(0) = nums[0].

6. One recursion call

Suppose i = 4 and nums[4] = 2.

solve(4)
start new
2
extend
2 + solve(3)

solve(3) does not mean the answer for the whole array. It only means the best subarray sum that ends exactly at index 3.

7. Pure recursive solution

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)

        def solve(i):
            # Maximum subarray sum that must end at index i
            if i == 0:
                return nums[0]

            start_new = nums[i]
            extend_previous = nums[i] + solve(i - 1)

            return max(start_new, extend_previous)

        answer = float('-inf')

        for i in range(n):
            answer = max(answer, solve(i))

        return answer
This version is useful for understanding the recurrence, but it recomputes the same states many times.

8. Why do we still need a global answer?

solve(i) = best sum ending at i

The maximum subarray may end at any index, so the final answer is:

max(solve(0), solve(1), ..., solve(n - 1))

9. Memoized recursion

class Solution:
    def maxSubArray(self, nums):
        memo = {}

        def solve(i):
            if i == 0:
                return nums[0]

            if i in memo:
                return memo[i]

            memo[i] = max(
                nums[i],
                nums[i] + solve(i - 1)
            )

            return memo[i]

        answer = float('-inf')

        for i in range(len(nums)):
            answer = max(answer, solve(i))

        return answer

10. Values for the example

11. From top-down to iteration

In the memoized version, solve(i) uses only solve(i - 1). Compute the states in order, starting with solve(0) = nums[0]. Then a single variable can hold the previous state instead of a memo dictionary.

previous_current = solve(i - 1)
current = solve(i) = max(nums[i], nums[i] + previous_current)

Keep answer as well: current is the best sum ending at this index, while answer is the best sum across all indices. This iterative form is Kadane's Algorithm.

12. The same recurrence, written iteratively

The choices are the same as in solve(i): start at i or extend the best subarray ending at i - 1. Iteration also avoids Python's recursion depth limit for large inputs. 

class Solution:
    def maxSubArray(self, nums):
        current = nums[0]
        answer = nums[0]

        for i in range(1, len(nums)):
            previous_current = current  # solve(i - 1)
            start_new = nums[i]
            extend_previous = nums[i] + previous_current
            current = max(start_new, extend_previous)  # solve(i)
            answer = max(answer, current)

        return answer