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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.