Maximum Product Subarray [Solution]

Solution 1: Dynamic Programming

This solution uses a dynamic programming approach with two variables to keep track of the maximum and minimum product of subarrays ending at each index. The time complexity is O(n), and the space complexity is O(1).

Here’s a Python implementation of the max_product function:

from typing import List

def max_product(nums: List[int]) -> int:
    if not nums:
        return 0

    # Initialize variables to keep track of the maximum and minimum product of subarrays
    max_product_value = nums[0]
    min_product_value = nums[0]
    result = max_product_value

    # Iterate through the array starting from the second element
    for num in nums[1:]:
        # If the current number is negative, swap the max and min values
        if num < 0:
            max_product_value, min_product_value = min_product_value, max_product_value

        # Update the max and min product values for the current element
        max_product_value = max(num, max_product_value * num)
        min_product_value = min(num, min_product_value * num)

        # Update the overall result with the maximum product value
        result = max(result, max_product_value)

    return result

# Example usage:
nums = [2, 3, -2, 4]
result = max_product(nums)
print(result)  # Output: 6

nums = [-2, 0, -1]
result = max_product(nums)
print(result)  # Output: 0

nums = [1,2,-2, 100, -2]
result = max_product(nums)
print(result)  # Output: 800

This solution maintains two variables, max_product and min_product, to keep track of the maximum and minimum products of subarrays ending at the current element. This approach handles negative numbers correctly by swapping max_product and min_product when encountering a negative number. The result is updated with the maximum product found so far. Finally, the function returns the maximum product found.

Time Complexity:

• The solution involves iterating through the given array once, which takes O(n) time, where n is the length of the input array nums.
• Within the loop, there are constant-time operations like comparisons and arithmetic operations.
• Thus, the overall time complexity of the solution is O(n).

Space Complexity:

• The solution uses only a constant amount of extra space regardless of the size of the input array. It maintains a few variables (max_product, min_product, result) to keep track of the maximum product subarray, minimum product subarray, and the final result.
• Hence, the space complexity of the solution is O(1), indicating constant space usage.

Solution 2: Brute Force

Another intuitive solution involves a straightforward approach using a brute-force method. Although this solution might not be the most efficient for large arrays, it provides a clear and easy-to-understand way to solve the problem.

Here’s the idea:

• Generate all possible subarrays of the given array.
• Calculate the product of each subarray.
• Keep track of the maximum product found during this process.
• Return the maximum product found.

While this solution might not be the most efficient due to its quadratic time complexity, it can be helpful for small input sizes or for educational purposes to understand the problem better.

Here’s how you can implement this approach in Python:

from typing import List

def max_product_subarray(nums: List[int]) -> int:
    if not nums:
        return 0
    
    # Initialize maximum product to negative infinity
    max_product = float('-inf')
    
    # Iterate over each index 'i' in the array
    for i in range(len(nums)):

        # Initialize product of subarray starting at index 'i' to 1
        product = 1
        
        # Iterate over each index 'j' starting from 'i' to the end of the array
        for j in range(i, len(nums)):

            # Calculate product of subarray [nums[i], nums[i+1], ..., nums[j]]
            product *= nums[j]

            # Update maximum product if necessary
            max_product = max(max_product, product)  
    
    return max_product

# Example usage:
print(max_product_subarray([2, 3, -2, 4]))  # Output: 6
print(max_product_subarray([-2, 0, -1]))   # Output: 0
print(max_product_subarray([1,2,-2, 100, -2]))   # Output: 800

While this solution is easy to understand, it’s important to note that it’s not the most efficient, especially for large arrays, due to its quadratic time complexity. However, it can serve as a starting point for understanding the problem before exploring more optimized solutions like dynamic programming above.

Time Complexity:

Generating all possible subarrays requires iterating through the array twice: once for the start index and once for the end index. This results in nested loops, leading to O(n^2) iterations, where n is the length of the input array nums.

Space Complexity:

The brute-force solution doesn’t use any additional space proportional to the input size. It only uses a few variables (max_product, product, i, j) to keep track of the maximum product and indices during the computation. Hence, the space complexity of the brute-force solution is O(1), indicating constant space usage.