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:
- Initialize two variables:
max_currentandmax_global. Set both to the first element of the array. - Iterate through the array starting from the second element.
- For each element, update
max_currentto be the maximum of the current element itself or the sum ofmax_currentand the current element. This step decides whether to start a new subarray at the current element or to continue the existing subarray. - Update
max_globalto be the maximum ofmax_globalandmax_current. This keeps track of the largest sum encountered so far. - After iterating through the array,
max_globalwill 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_currentandmax_globalto 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_currentwhen it becomes negative.
The solution provided is correct, efficient, and clear. It adheres to the constraints and handles all edge cases appropriately.