Maximum Product Subarray - Leetcode Solution

The Maximum Product Subarray problem is a classic problem in computer science. It can be solved using dynamic programming.

The problem statement is as follows:

Given an array of integers, find the contiguous subarray within it that has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product 6.

Solution:

We can solve this problem using dynamic programming. The key to solving this problem is recognizing that the maximum product subarray can be computed from the maximum product of the subarray ending at each position.

We will maintain two arrays:

1. max_product[i] stores the maximum product of the subarray ending at position i.
2. min_product[i] stores the minimum product of the subarray ending at position i.

We will then update these arrays at each position using the following equations:

1. max_product[i] = max(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])
2. min_product[i] = min(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])

The max_product[i] and min_product[i] represent the maximum and minimum product of subarrays ending at position i, respectively. If the current number nums[i] is positive, then the maximum and minimum product of subarrays ending at position i is either nums[i] itself or the maximum and minimum product of subarrays ending at position i-1 times nums[i]. If nums[i] is negative, then the maximum and minimum product of subarrays ending at position i is either nums[i] itself or the minimum and maximum product of subarrays ending at position i-1 times nums[i].

Finally, we return the maximum value in max_product.

Here is the implementation of the solution in Python:

def maxProduct(nums: List[int]) -> int:
    max_product = [0] * len(nums)
    min_product = [0] * len(nums)

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

    for i in range(1, len(nums)):
        if nums[i] >= 0:
            max_product[i] = max(nums[i], max_product[i-1] * nums[i])
            min_product[i] = min(nums[i], min_product[i-1] * nums[i])
        else:
            max_product[i] = max(nums[i], min_product[i-1] * nums[i])
            min_product[i] = min(nums[i], max_product[i-1] * nums[i])

    return max(max_product)

The time complexity of this solution is O(N), where N is the length of the input array. The space complexity is O(N), since we use two arrays to store the maximum and minimum product of subarrays ending at each position.

1