How can Dynamic Programming be used to solve the Maximum Product Subarray problem?

To solve the Maximum Product Subarray problem using Dynamic Programming, we can use a bottom-up approach.

First, we define two arrays, max_product and min_product, both of size n, where n is the length of the input array. The max_product array will store the maximum product subarray ending at each index, while the min_product array will store the minimum product subarray ending at each index.

We initialize the first element of both arrays with the first element of the input array, as it will be the only element in the subarray.

Then, we iterate through the input array starting from the second element. At each index i, we update the max_product[i] and min_product[i] based on the following conditions:

1. If the current element is positive, we can either extend the maximum product subarray by multiplying it with the previous maximum product (max_product[i-1]) or start a new subarray from the current element. Therefore, max_product[i] will be the maximum of the current element and the product of the current element and max_product[i-1]. Similarly, min_product[i] will be the minimum of the current element and the product of the current element and min_product[i-1].

2. If the current element is negative, we can either extend the maximum product subarray by multiplying it with the previous minimum product (min_product[i-1]) or start a new subarray from the current element. Therefore, max_product[i] will be the maximum of the current element and the product of the current element and min_product[i-1]. Similarly, min_product[i] will be the minimum of the current element and the product of the current element and max_product[i-1].

3. If the current element is zero, both max_product[i] and min_product[i] will be zero, as any subarray containing a zero element will have a product of zero.

After iterating through the entire input array, the maximum product subarray can be obtained by finding the maximum element in the max_product array.

The time complexity of this approach is O(n), where n is the length of the input array, as we only need to iterate through the array once.