LeetCode #152: Maximum Product Subarray

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

We can solve this problem using Dynamic Programming approach. We will maintain the maximum and minimum subarray product ending at every index i, which can be either a single element or the product of maximum and minimum subarray product ending at index i-1.

Algorithm:

1. Initialize the maximum and minimum subarray product as 1 and res as nums[0].
2. Iterate over the nums array, for every index i: a. If the current element is negative, swap the maximum and minimum subarray product values. b. Calculate the current maximum and minimum subarray product values, taking into account the current element. c. Update the maximum subarray product value as maximum of the current maximum and previous maximum subarray product values.
3. Return the maximum subarray product value.

Here is the solution in python3:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]
        cur_min, cur_max = 1, 1
        for n in nums:
            tmp = cur_max * n
            cur_max = max(n * cur_max, n * cur_min, n)
            cur_min = min(tmp, n * cur_min, n)
            res = max(res, cur_max)
        return res

Time Complexity: The time complexity of the above solution is O(n), where n is the length of the input nums array.

Space Complexity: The space complexity of the above solution is O(1), as we are not using any extra space.