152. Maximum Product Subarray

Problem Statement

link: https://leetcode.com/problems/maximum-product-subarray/ https://leetcode.cn/problems/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:

Input: nums = [2,3,-2,4] Output: 6

Input: nums = [-2,0,-1] Output: 0

Solution Approach

The solution capitalizes on the properties of multiplication and tracks both the maximum and minimum products ending at the current position, as the minimum product can turn into maximum when multiplied by a negative number.

Algorithm

1. Initialize two arrays, dpMax and dpMin, to keep track of the maximum and minimum product subarrays ending at position i. Start both arrays with the first element of nums.
2. Iterate through nums starting from the second element. For each i, update dpMax[i] as the maximum of (dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i], nums[i]) and similarly, update dpMin[i] considering the potential negative multiplication scenarios.
3. Keep track of the global maximum during iteration, which is our result.

Implement

    class Solution:
  def maxProduct(self, nums: List[int]) -> int:
      n = len(nums)
      if n == 1:
          return nums[0]
      dpMax = [0] * n
      dpMax[0] = nums[0]
      dpMin = [0] * n
      dpMin[0] = nums[0]
      res = nums[0]
      for i in range(1, n):
          dpMax[i] = max(max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i])
          dpMin[i] = min(min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i])
          res = max(dpMax[i], res)
      return res

      
 

    
    

Twitter  facebook  Email