Problem Description

You are given an integer array nums. Your task is to find a contiguous subarray (containing at least one element) that has the largest sum and return that sum.

A subarray is a contiguous part of an array. For example, if nums = [1, 2, 3, 4], then [2, 3] is a subarray, but [1, 3] is not (elements are not contiguous).

The problem asks you to examine all possible contiguous subarrays and determine which one produces the maximum sum. You need to return only the sum value, not the actual subarray elements.

For instance:

• If nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray [4, -1, 2, 1] has the largest sum of 6.
• If nums = [1], the only subarray is [1] with sum 1.
• If nums = [5, 4, -1, 7, 8], the entire array forms the maximum sum subarray with sum 23.

The array will contain at least one element, and elements can be positive, negative, or zero.

Intuition

When looking for the maximum sum of a contiguous subarray, we need to make a decision at each element: should we extend the current subarray to include this element, or should we start a new subarray from this element?

Think about it this way - as we traverse the array from left to right, at each position we're maintaining the best subarray that ends at that specific position. For any element at index i, we have two choices:

1. Add the current element to the existing subarray ending at position i-1 (extend the previous subarray)
2. Start a fresh subarray beginning from the current element

The key insight is that we should extend the previous subarray only if it contributes positively to our sum. If the previous subarray sum is negative, adding it to the current element would only decrease our total, so we're better off starting fresh from the current element.

This leads to the formula: f[i] = max(f[i-1] + nums[i], nums[i]), which can be rewritten as f[i] = max(f[i-1], 0) + nums[i].

The beauty of this approach is that we don't need to check every possible subarray explicitly. By maintaining the best subarray ending at each position and keeping track of the overall maximum seen so far, we can solve the problem in a single pass through the array.

For example, with array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

• At index 0: best ending here is -2
• At index 1: previous sum -2 is negative, so start fresh with 1
• At index 2: extend with 1 + (-3) = -2
• At index 3: previous sum -2 is negative, so start fresh with 4
• And so on...

Throughout this process, we keep track of the maximum sum encountered, which gives us our final answer.

Learn more about Divide and Conquer and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with space optimization. Let's break down the implementation:

We define f[i] to represent the maximum sum of a contiguous subarray ending at element nums[i]. The state transition equation is:

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

Which can be rewritten as:

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

This means at each position, we either extend the previous subarray (if f[i-1] > 0) or start a new subarray from the current element (if f[i-1] ≤ 0).

Space Optimization:

Since f[i] only depends on f[i-1], we don't need to maintain an entire array. We can use a single variable f to track the current maximum subarray sum ending at the current position.

Implementation walkthrough:

def maxSubArray(self, nums: List[int]) -> int:
    ans = f = nums[0]  # Initialize both answer and current sum with first element
    for x in nums[1:]:  # Iterate through remaining elements
        f = max(f, 0) + x  # Update current max sum ending at this position
        ans = max(ans, f)  # Update global maximum
    return ans

1. Initialization: We start with ans = f = nums[0]. Both the global maximum (ans) and the current subarray sum (f) are initialized to the first element.

2. Iteration: For each subsequent element x:

   • f = max(f, 0) + x: If the previous sum f is negative, we reset it to 0 (effectively starting a new subarray). Then we add the current element.
   • ans = max(ans, f): We update our global maximum if the current subarray sum is larger.

3. Return: The variable ans maintains the maximum sum seen across all positions.

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) - only using two variables regardless of input size

This approach efficiently solves the maximum subarray problem by making optimal local decisions at each step while maintaining the global maximum.

Example Walkthrough

Let's walk through the solution with the array nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

We'll track two variables:

• f: maximum sum of subarray ending at current position
• ans: global maximum sum seen so far

Initial State:

• f = nums[0] = -2 (subarray ending at index 0)
• ans = -2 (global maximum so far)

Step 1: Process element 1 (index 1)

• f = max(f, 0) + x = max(-2, 0) + 1 = 0 + 1 = 1
  • Since previous sum (-2) is negative, we start fresh from current element
• ans = max(ans, f) = max(-2, 1) = 1
• Current best subarray ending here: [1]

Step 2: Process element -3 (index 2)

• f = max(1, 0) + (-3) = 1 + (-3) = -2
  • Previous sum (1) is positive, so we extend the subarray
• ans = max(1, -2) = 1
• Current best subarray ending here: [1, -3]

Step 3: Process element 4 (index 3)

• f = max(-2, 0) + 4 = 0 + 4 = 4
  • Previous sum (-2) is negative, so we start fresh
• ans = max(1, 4) = 4
• Current best subarray ending here: [4]

Step 4: Process element -1 (index 4)

• f = max(4, 0) + (-1) = 4 + (-1) = 3
  • Previous sum (4) is positive, so we extend
• ans = max(4, 3) = 4
• Current best subarray ending here: [4, -1]

Step 5: Process element 2 (index 5)

• f = max(3, 0) + 2 = 3 + 2 = 5
  • Previous sum (3) is positive, so we extend
• ans = max(4, 5) = 5
• Current best subarray ending here: [4, -1, 2]

Step 6: Process element 1 (index 6)

• f = max(5, 0) + 1 = 5 + 1 = 6
  • Previous sum (5) is positive, so we extend
• ans = max(5, 6) = 6
• Current best subarray ending here: [4, -1, 2, 1]

Step 7: Process element -5 (index 7)

• f = max(6, 0) + (-5) = 6 + (-5) = 1
  • Previous sum (6) is positive, so we extend
• ans = max(6, 1) = 6
• Current best subarray ending here: [4, -1, 2, 1, -5]

Step 8: Process element 4 (index 8)

• f = max(1, 0) + 4 = 1 + 4 = 5
  • Previous sum (1) is positive, so we extend
• ans = max(6, 5) = 6
• Current best subarray ending here: [4, -1, 2, 1, -5, 4]

Final Result: The maximum subarray sum is 6, achieved by the subarray [4, -1, 2, 1].

The key insight illustrated here is how the algorithm decides at each step whether to extend the current subarray or start fresh, always keeping track of the best sum seen overall.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once using a single for loop that processes each element from index 1 to the end of the array.

The space complexity is O(1). The algorithm only uses a constant amount of extra space, maintaining two variables ans and f regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling All Negative Numbers Incorrectly

A frequent mistake occurs when implementing Kadane's algorithm without proper initialization, particularly when the array contains only negative numbers.

Incorrect Implementation:

def maxSubArray(self, nums: List[int]) -> int:
    max_sum = 0  # Wrong initialization!
    current_sum = 0
  
    for num in nums:
        current_sum = max(current_sum + num, 0)  # Resets to 0
        max_sum = max(max_sum, current_sum)
  
    return max_sum

Problem: If nums = [-3, -2, -5, -1], this returns 0, but the correct answer is -1 (the single element with minimum negative value).

Solution: Always initialize max_sum with the first element or negative infinity, never with 0:

max_sum = current_sum = nums[0]  # Correct
# OR
max_sum = float('-inf')  # Also correct

2. Confusion Between "Reset to 0" vs "Reset to Current Element"

Some implementations incorrectly reset the current sum:

Incorrect Implementation:

def maxSubArray(self, nums: List[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
  
    for num in nums[1:]:
        current_sum = max(current_sum + num, 0)  # Wrong reset logic!
        max_sum = max(max_sum, current_sum)
  
    return max_sum

Problem: The line current_sum = max(current_sum + num, 0) can produce 0 even when we should keep negative values. For nums = [-1], this might return 0 instead of -1.

Solution: The correct comparison should be between extending the previous subarray or starting fresh from the current element:

current_sum = max(current_sum + num, num)  # Correct
# OR equivalently
current_sum = max(current_sum, 0) + num  # Also correct

3. Off-by-One Errors in Iteration

When manually managing indices, it's easy to make boundary errors:

Incorrect Implementation:

def maxSubArray(self, nums: List[int]) -> int:
    if not nums:
        return 0
  
    max_sum = current_sum = nums[0]
  
    for i in range(len(nums)):  # Should start from 1, not 0!
        current_sum = max(current_sum, 0) + nums[i]
        max_sum = max(max_sum, current_sum)
  
    return max_sum

Problem: This processes the first element twice - once in initialization and once in the loop.

Solution: Start iteration from index 1 or use slicing:

for i in range(1, len(nums)):  # Start from 1
    current_sum = max(current_sum, 0) + nums[i]
# OR
for num in nums[1:]:  # Skip first element with slicing
    current_sum = max(current_sum, 0) + num

4. Not Updating Maximum After Each Calculation

Forgetting to track the global maximum at each step:

Incorrect Implementation:

def maxSubArray(self, nums: List[int]) -> int:
    current_sum = 0
  
    for num in nums:
        current_sum = max(current_sum, 0) + num
  
    return current_sum  # Returns last subarray sum, not maximum!

Problem: This returns the sum of the subarray ending at the last element, not the maximum sum overall.

Solution: Maintain a separate variable for the global maximum and update it after each calculation:

max_sum = float('-inf')
current_sum = 0

for num in nums:
    current_sum = max(current_sum, 0) + num
    max_sum = max(max_sum, current_sum)  # Track global maximum

return max_sum