🟨 Maximum Product Subarray (#152)
🔗 Problem Link
📋 Problem Statement
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
💡 Examples
Example 1
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2
Input: nums = [-2,0,-1]
Output: 0
🔑 Key Insights & Approach
Core Observation: Track both max and min products (negative * negative = positive). Reset on zero.
Why Track Min?
- Negative number can flip min to max
- O(n) time, O(1) space
- Kadane's algorithm variant
Pattern: "Dynamic Max/Min Tracking" pattern.
🐍 Solution: Python
Approach: Track Max and Min
Time Complexity: O(n) | Space Complexity: O(1)
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
max_prod = min_prod = result = nums[0]
for i in range(1, len(nums)):
num = nums[i]
# Calculate candidates
temp_max = max(num, max_prod * num, min_prod * num)
min_prod = min(num, max_prod * num, min_prod * num)
max_prod = temp_max
result = max(result, max_prod)
return result
🔵 Solution: Golang
Approach: Track Max and Min
Time Complexity: O(n) | Space Complexity: O(1)
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
maxProd, minProd, result := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
num := nums[i]
tempMax := max(num, max(maxProd*num, minProd*num))
minProd = min(num, min(maxProd*num, minProd*num))
maxProd = tempMax
result = max(result, maxProd)
}
return result
}
func max(a, b int) int {
if a > b { return a }
return b
}
func min(a, b int) int {
if a < b { return a }
return b
}