Maximum product contiguous subarray

Question

I have come up with the following solution to find the maximum product for a contiguous sub-array:

def maxProduct(nums):
    
    max_prod = [0]*len(nums)
    min_prod = [0]*len(nums)
    for i in range(0, len(nums)):
        min_prod[i] = min(nums[i], min_prod[i-1]*nums[i], max_prod[i-1]*nums[i])
        max_prod[i] = max(nums[i], min_prod[i-1]*nums[i], max_prod[i-1]*nums[i])
        
   
    return max(max_prod)

Current solution is O(n) in space, trying to find O(1) solution for space, but I keep seem to missing it. Ideas?

Answer 1

1. Follow PEP8 style guide for variable and function naming convention. Both the variables and function names should have snake_case names.
2. You can use enumerate to get index and value while iterating a list.

---

For constant space solution, instead of using a list to keep track of current max and min products, use a variable for both positive product and negative product. If the current number is \$ 0 \$, reset them both to \$ 1 \$ (They should be initialised as \$ 1 \$ as well). At the end of for-loop (inside the loop), keep updating your current_max value to keep track of max product encountered so far.

---

As edge cases, you may also consider returning (or raising errors) when input was empty etc.