Maximum Subarray and Maximum Product Subarray
Apply Kadane's algorithm to maximum-sum-subarray and extend it to track both maximum and minimum for the product variant.
Maximum Sum Subarray Problem
The Maximum Subarray problem asks you to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] gives the maximum sum of 6. A brute-force O(n²) approach checks all subarrays, but Kadane's algorithm solves it in O(n).
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6Kadane's Algorithm Intuition
Kadane's algorithm makes one pass through the array, maintaining a running current_sum. At each element, you decide: is it better to extend the existing subarray or start fresh from this element? If current_sum becomes negative, it would only hurt any future subarray, so restart. The recurrence is current_sum = max(num, current_sum + num).
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths