MediumNeetCode150ArrayDivide and ConquerDynamic Programming
Maximum Subarray
Find contiguous subarray with largest sum.
Examples
Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6
[4,-1,2,1] has sum 6.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4
Approaches
Check all subarrays.
CodeT: O(n^2) | S: O(1)
dp[i] = max(nums[i], dp[i-1]+nums[i]).
CodeT: O(n) | S: O(n)
Same approach.
CodeT: O(n) | S: O(1)
def maxSubArray(nums):
ms=cs=nums[0]
for n in nums[1:]:
cs=max(n,cs+n); ms=max(ms,cs)
return msComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all subarrays. |
| Kadane's Algorithm | O(n) | O(n) | dp[i] = max(nums[i], dp[i-1]+nums[i]). |
| Kadane's Optimized | O(n) | O(1) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Check all subarrays.
Kadane's Algorithm
T: O(n)S: O(n)
dp[i] = max(nums[i], dp[i-1]+nums[i]).
Kadane's Optimized
T: O(n)S: O(1)
Same approach.
Common Mistakes
Not handling all negative numbers
Off-by-one
Wrong initialization