Maximum Product Subarray

Question:

Given an integer array nums, find the contiguous subarray within the array that has the largest product, and return the product.

Example:

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

Explanation: The subarray [2,3] has the largest product, which is 2 * 3 = 6.

Instructions:

• Implement the function maxProduct(nums: List[int]) -> int, where:
  • nums: a list of integers representing the input array.
  • Returns the maximum product of any contiguous subarray within nums.

Note:

• The input array can have both positive and negative integers.
• The length of the input array will be in the range [1, 2 * 10^4].
• The product of any prefix or suffix of the input array may not fit in a 32-bit integer, so the expected answer might be a large number.

Answer:

To solve this problem, we can use a dynamic programming approach. Let's follow these steps:

1. Initialize two variables:

   • max_product to store the maximum product found so far.
   • min_product to store the minimum product found so far.

2. Set the initial values of max_product and min_product to the first element of the input array:

   • max_product = nums[0]
   • min_product = nums[0]

3. Initialize a variable result to store the final maximum product, initially set to the first element of the input array:

   • result = nums[0]

4. Iterate over the input array starting from the second element.

5. At each iteration, update the values of max_product and min_product as follows:

   • Calculate the product of the current element with the max_product and min_product of the previous subarray.
   • Update max_product to the maximum value among the current element, the previous max_product multiplied by the current element, or the previous min_product multiplied by the current element.
   • Update min_product to the minimum value among the current element, the previous max_product multiplied by the current element, or the previous min_product multiplied by the current element.

6. After updating max_product and min_product, update result to the maximum value among result and max_product.

7. Finally, return result as the maximum product of any contiguous subarray within nums.

Here's the implementation of the solution in Python:

from typing import List

def maxProduct(nums: List[int]) -> int:
    if not nums:
        return 0
    
    max_product = nums[0]
    min_product = nums[0]
    result = nums[0]
    
    for i in range(1, len(nums)):
        # Calculate the product at current index
        current_product = nums[i]
        
        # Update max_product using current element
        temp_max = max(current_product, max_product * current_product, min_product * current_product)
        max_product = max(temp_max, current_product)
        
        # Update min_product using current element
        temp_min = min(current_product, max_product * current_product, min_product * current_product)
        min_product = min(temp_min, current_product)
        
        # Update result to maximum value so far
        result = max(result, max_product)
    
    return result

The time complexity of this solution is O(n), where n is the length of the input array nums, as we iterate over the array once.