loading

53. Maximum Subarray — Step-by-Step Visualization

mediumLeetCode #53ArrayDynamic Programming

Given an integer array `nums`, find the subarray with the largest sum, and return its sum. **Example 1:** Input: `nums = [-2,1,-3,4,-1,2,1,-5,4]` Output: `6` Explanation: The subarray `[4,-1,2,1]` has the largest sum `6`. **Example 2:** Input: `nums = [1]` Output: `1` **Example 3:** Input: `nums = [5,4,-1,7,8]` Output: `23`

Algorithm Pattern

Kadane's Algorithm

Key Idea

For each element, we decide whether to start a new subarray beginning at that element, or extend the previous subarray. This is a local choice that leads to a global maximum.

Step-by-Step Approach

  1. Initialize `maxSum` and `currentSum` with the first element's value.
  2. Iterate through the array starting from the second element.
  3. For each element `n`:
  4. 1. Update `currentSum`: `currentSum = max(n, currentSum + n)`.
  5. 2. Update `maxSum`: `maxSum = max(maxSum, currentSum)`.
  6. Return `maxSum`.

Common Gotchas

  • If the array contains only negative numbers, `maxSum` should be the largest (least negative) single number.
  • A common mistake is initializing `maxSum` to 0, which fails if all numbers are negative.

Related Problems

← All problems