https://leetcode.com/problems/maximum-product-subarray

Let dp1[i] be the maximum product which ends with i-th index and dp2[i] be the minimum product which ends with i-the index. Why we need both maximum and minimum? Because we can have big negative number, which then multiplied by negative will give big positive number.

So, let us traverse all numbers and update our dp1 and dp2:

  1. If nums[k] > 0, then biggest number dp1[k] can be found as maximum of dp1[k-1] * nums[k] and nums[k]. The smallest number dp2[k] is equal to minimum of dp2[k-1] * nums[k] and nums[k]
  2. If nums[k] <= 0, then the biggest number is maximum of dp2[k-1] * nums[k] and nums[k] and the smalles number dp2[k] is minimum of dp1[k-1] * nums[k] and nums[k]
  3. Finally, we return maximum of dp1.

Complexity: both time and space is O(n). Space complexity can be improved to O(1), because we always use only previous elements in our dp1 and dp2 tables.

class Solution:
    def maxProduct(self, nums):
        N = len(nums)
        dp1 = [0] * N
        dp2 = [0] * N
        dp1[0] = dp2[0] = nums[0]
        
        for k in range(1, N):
            if nums[k] > 0:
                dp1[k] = max(dp1[k-1] * nums[k], nums[k])
                dp2[k] = min(dp2[k-1] * nums[k], nums[k])
            else:
                dp1[k] = max(dp2[k-1] * nums[k], nums[k])
                dp2[k] = min(dp1[k-1] * nums[k], nums[k])
        
        return max(dp1)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0152