LeetCode 53: Maximum Subarray Solution in Python Explained

Problem Statement

LeetCode 53, Maximum Subarray, is a medium-level problem where you’re given an integer array nums. Your task is to find the contiguous subarray (containing at least one element) with the largest sum and return that sum. This is a classic problem often solved efficiently with Kadane’s Algorithm.

Constraints

  • 1 <= nums.length <= 10^5: Array length is between 1 and 100,000.
  • -10^4 <= nums[i] <= 10^4: Each element is within this range.

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has the largest sum = 6.

Input: nums = [1]
Output: 1
Explanation: Single element subarray [1] has sum = 1.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Entire array [5,4,-1,7,8] sums to 23, the maximum.

Understanding the Problem

How do you solve LeetCode 53: Maximum Subarray in Python? For nums = [-2,1,-3,4,-1,2,1,-5,4], find the contiguous subarray with the largest sum—here, [4,-1,2,1] sums to 6. We need an efficient way to scan the array and track the maximum sum. We’ll explore two approaches: a Kadane’s Algorithm Solution (optimal and primary) and an Alternative with Divide and Conquer (more complex but insightful). Kadane’s method runs in O(n) time by maintaining a running maximum sum.

Solution 1: Kadane’s Algorithm Approach (Primary)

Explanation

Kadane’s Algorithm iterates through the array, keeping track of the maximum sum ending at the current position (curr_max) and the overall maximum sum seen so far (global_max). At each step, decide whether to start a new subarray at the current element or extend the existing subarray by adding the current element.

Here’s a flow for [-2,1,-3,4,-1,2,1,-5,4]:

i=0: curr_max = -2, global_max = -2
i=1: curr_max = 1, global_max = 1
i=2: curr_max = -2, global_max = 1
i=3: curr_max = 4, global_max = 4
i=4: curr_max = 3, global_max = 4
i=5: curr_max = 5, global_max = 5
i=6: curr_max = 6, global_max = 6
i=7: curr_max = 1, global_max = 6
i=8: curr_max = 5, global_max = 6
  1. Initialize Variables.
  • curr_max and global_max start with the first element.
  1. Iterate Array.
  • Update curr_max as max(current element, curr_max + current element).
  • Update global_max if curr_max exceeds it.
  1. Return Result.
  • global_max is the maximum subarray sum.

Step-by-Step Example

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

We need 6.

  • Goal: Find maximum subarray sum.
  • Result for Reference: 6.
  • Start: nums = [-2,1,-3,4,-1,2,1,-5,4], curr_max = -2, global_max = -2.
  • Step 1: i = 0, nums[0] = -2.
    • curr_max = -2, global_max = -2.
  • Step 2: i = 1, nums[1] = 1.
    • curr_max = max(1, -2+1) = 1, global_max = 1.
  • Step 3: i = 2, nums[2] = -3.
    • curr_max = max(-3, 1-3) = -2, global_max = 1.
  • Step 4: i = 3, nums[3] = 4.
    • curr_max = max(4, -2+4) = 4, global_max = 4.
  • Step 5: i = 4, nums[4] = -1.
    • curr_max = max(-1, 4-1) = 3, global_max = 4.
  • Step 6: i = 5, nums[5] = 2.
    • curr_max = max(2, 3+2) = 5, global_max = 5.
  • Step 7: i = 6, nums[6] = 1.
    • curr_max = max(1, 5+1) = 6, global_max = 6.
  • Step 8: i = 7, nums[7] = -5.
    • curr_max = max(-5, 6-5) = 1, global_max = 6.
  • Step 9: i = 8, nums[8] = 4.
    • curr_max = max(4, 1+4) = 5, global_max = 6.
  • Finish: Return 6.

Example 2: nums = [5,4,-1,7,8]

We need 23.

  • Start: curr_max = 5, global_max = 5.
  • Step 1: i = 1, nums[1] = 4.
    • curr_max = 9, global_max = 9.
  • Step 2: i = 2, nums[2] = -1.
    • curr_max = 8, global_max = 9.
  • Step 3: i = 3, nums[3] = 7.
    • curr_max = 15, global_max = 15.
  • Step 4: i = 4, nums[4] = 8.
    • curr_max = 23, global_max = 23.
  • Finish: Return 23.

How the Code Works (Kadane’s Algorithm)

Here’s the Python code with line-by-line explanation:

def maxSubArray(nums: list[int]) -> int:
    # Line 1: Initialize current and global max
    curr_max = global_max = nums[0]

    # Line 2: Iterate through array
    for i in range(1, len(nums)):
        # Line 3: Update current max
        curr_max = max(nums[i], curr_max + nums[i])
        # Line 4: Update global max
        global_max = max(global_max, curr_max)

    # Line 5: Return maximum subarray sum
    return global_max

Alternative: Divide and Conquer Approach

Explanation

Use divide and conquer to split the array into left and right halves, recursively finding the maximum subarray sum in each half and the maximum crossing the midpoint. Combine these to get the overall maximum.

  1. Base Case.
  • Single element, return it.
  1. Divide.
  • Split array, recurse on halves.
  1. Conquer.
  • Compute max crossing sum, combine with left and right.
  1. Return Result.

Step-by-Step Example (Alternative)

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

  • Start: Split at mid = 4.
  • Left: [-2,1,-3,4], recurse.
    • Left: [-2,1], max = 1.
    • Right: [-3,4], max = 4.
    • Cross: [-3,4], max = 4.
    • Max = 4.
  • Right: [-1,2,1,-5,4], recurse.
    • Left: [-1,2], max = 2.
    • Right: [1,-5,4], max = 4.
    • Cross: [1,-5,4], max = 4.
    • Max = 4.
  • Cross: From mid=4, left max = 4, right max = 2, total = 6.
  • Finish: Max of left (4), right (4), cross (6) = 6.

How the Code Works (Divide and Conquer)

def maxSubArrayDC(nums: list[int]) -> int:
    # Line 1: Helper for divide and conquer
    def maxCrossingSum(nums: list[int], left: int, mid: int, right: int) -> int:
        # Line 2: Max sum crossing to left
        left_sum = float('-inf')
        curr_sum = 0
        for i in range(mid, left - 1, -1):
            curr_sum += nums[i]
            left_sum = max(left_sum, curr_sum)

        # Line 3: Max sum crossing to right
        right_sum = float('-inf')
        curr_sum = 0
        for i in range(mid + 1, right + 1):
            curr_sum += nums[i]
            right_sum = max(right_sum, curr_sum)

        # Line 4: Return total crossing sum
        return left_sum + right_sum

    # Line 5: Recursive helper
    def maxSubArrayHelper(nums: list[int], left: int, right: int) -> int:
        # Line 6: Base case
        if left == right:
            return nums[left]

        # Line 7: Divide
        mid = (left + right) // 2

        # Line 8: Conquer: max of left, right, and crossing
        return max(maxSubArrayHelper(nums, left, mid),
                  maxSubArrayHelper(nums, mid + 1, right),
                  maxCrossingSum(nums, left, mid, right))

    # Line 9: Call helper and return
    return maxSubArrayHelper(nums, 0, len(nums) - 1)

Complexity

  • Kadane’s Algorithm:
    • Time: O(n) – Single pass through array.
    • Space: O(1) – Only two variables.
  • Divide and Conquer:
    • Time: O(n log n) – Log n levels, O(n) per level.
    • Space: O(log n) – Recursion stack.

Efficiency Notes

Kadane’s is O(n) time and O(1) space, optimal for LeetCode 53. Divide and Conquer is O(n log n) time and O(log n) space, less efficient but demonstrates a different strategy.

Key Insights

Tips to master LeetCode 53:

  • Kadane’s Core: Max of current or extend previous.
  • Local vs Global: Track both sums separately.
  • Negative Handling: Restart subarray when beneficial.

Additional Example

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

  • Goal: 3.
  • Kadane’s: curr_max = 3, global_max = 3.
  • Result: 3.

Edge Cases

  • Single Element: [1] – Return 1.
  • All Negative: [-2,-1] – Return -1.
  • All Positive: [1,2,3] – Return 6.

Final Thoughts

Kadane’s Algorithm is the gold standard for LeetCode 53 in Python—simple, fast, and space-efficient. For a related challenge, try LeetCode 52: N-Queens II to tackle a hard backtracking problem! Ready to sum it up? Solve LeetCode 53 on LeetCode now and test it with [-2,1,-3,4] or [1,2,3] to master maximum subarrays. Dive in and find the max!