{x}
blog image

Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

 

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
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Solution Explanation: Maximum Product Subarray

This problem asks to find the maximum product of a subarray within a given integer array. A naive approach would involve checking all possible subarrays, leading to a time complexity of O(n^3). However, a more efficient dynamic programming approach can solve this in O(n) time.

Approach:

The core idea is to track two values for each position i in the array:

  1. f[i] : The maximum product ending at index i.
  2. g[i] : The minimum product ending at index i.

We initialize both f[0] and g[0] to nums[0]. For each subsequent index i, we consider three possibilities:

  • The current element nums[i] itself.
  • The product of the current element and the previous maximum product (f[i-1] * nums[i]).
  • The product of the current element and the previous minimum product (g[i-1] * nums[i]).

f[i] is the maximum of these three, while g[i] is the minimum. The reason we need to track the minimum is because multiplying two negative numbers results in a positive number, potentially leading to a larger product. The overall maximum product is the maximum value encountered across all f[i].

Time Complexity Analysis:

The solution iterates through the input array nums once. Therefore, the time complexity is O(n), where n is the length of the array.

Space Complexity Analysis:

The solution uses a constant amount of extra space to store variables (f, g, ans). Therefore, the space complexity is O(1).

Code Explanation (Python):

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = f = g = nums[0]  # Initialize ans, f, and g to the first element
        for x in nums[1:]:       # Iterate from the second element
            ff, gg = f, g       # Store previous f and g values
            f = max(x, ff * x, gg * x) # Update f: max of current element, product with previous max, product with previous min
            g = min(x, ff * x, gg * x) # Update g: min of current element, product with previous max, product with previous min
            ans = max(ans, f)     # Update ans if a larger max product is found
        return ans

The other language implementations follow the same logic; they just use different syntax for the max and min functions and array iteration. The core algorithm remains the same, offering efficient computation of the maximum product subarray.