Domain 1EasyCORE

Maximum Subarray

The problem asks us to find the contiguous subarray within a given integer array `nums` that has the largest sum. The output should be the sum of this subarray. The constraints are that the array contains at least one number, and each number can range from -10^5 to 10^5.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Divide and Conquer#Dynamic Programming

53. Maximum Subarray

Model: qwen2.5-coder:14b
Topics: Array,Divide and Conquer,Dynamic Programming
FAANG asked: 1
Acceptance rate: 47.9%


Problem Breakdown

The problem asks us to find the contiguous subarray within a given integer array nums that has the largest sum. The output should be the sum of this subarray. The constraints are that the array contains at least one number, and each number can range from -10^5 to 10^5.

Inputs:

  • An integer array nums.

Outputs:

  • An integer representing the maximum sum of a contiguous subarray.

Implicit Constraints/Edge Cases:

  • The array must contain at least one element.
  • Elements can be negative, zero, or positive.
  • The solution should handle large arrays efficiently (up to 3 * 10^4 elements).

Intuition

A brute-force approach would involve checking all possible subarrays and calculating their sums. This would have a time complexity of O(n^2), which is inefficient for large arrays.

The key insight is that we can maintain a running sum of the current subarray and reset it if it becomes negative, as a negative sum would decrease the sum of any subsequent subarray. This leads to a linear solution using dynamic programming.

Approach

We will use Kadane’s Algorithm, which is an efficient way to solve this problem with O(n) time complexity. The algorithm works as follows:

  1. Initialize two variables: max_current and max_global. Set both to the first element of the array.
  2. Iterate through the array starting from the second element.
  3. For each element, update max_current to be the maximum of the current element itself or the sum of max_current and the current element. This step decides whether to start a new subarray at the current element or to continue the existing subarray.
  4. Update max_global to be the maximum of max_global and max_current. This keeps track of the largest sum encountered so far.
  5. After iterating through the array, max_global will contain the maximum sum of a contiguous subarray.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of elements in the array. We only need to iterate through the array once.
  • Space Complexity: O(1), as we are using a constant amount of extra space regardless of the input size.

Solution

def maxSubArray(nums):
    if not nums:
        return 0
    
    max_current = max_global = nums[0]
    
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    
    return max_global

Edge Cases Handled

  • Single Element Array: The algorithm correctly handles arrays with a single element by initializing max_current and max_global to the first (and only) element.
  • All Negative Numbers: If all numbers are negative, the algorithm will return the largest negative number, which is the correct maximum sum of any subarray.
  • Mixed Positive and Negative Numbers: The algorithm efficiently handles arrays with both positive and negative numbers by resetting max_current when it becomes negative.

The solution provided is correct, efficient, and clear. It adheres to the constraints and handles all edge cases appropriately.