What is the Maximum Product Subarray problem and how can it be solved using Dynamic Programming?

The Maximum Product Subarray problem is a problem in which we need to find the contiguous subarray within an array that has the largest product.

To solve this problem using Dynamic Programming, we can use two arrays: "max_product" and "min_product". The "max_product" array stores the maximum product ending at each index, while the "min_product" array stores the minimum product ending at each index.

We initialize both arrays with the first element of the given array. Then, for each subsequent element, we update the "max_product" and "min_product" arrays based on the current element and the previous values in the arrays.

The update rules are as follows:
1. If the current element is positive, we update the "max_product" array by taking the maximum of the current element and the product of the current element and the maximum product ending at the previous index. Similarly, we update the "min_product" array by taking the minimum of the current element and the product of the current element and the minimum product ending at the previous index.
2. If the current element is zero, we reset both the "max_product" and "min_product" arrays to zero.
3. If the current element is negative, we update the "max_product" array by taking the maximum of the current element and the product of the current element and the minimum product ending at the previous index. Similarly, we update the "min_product" array by taking the minimum of the current element and the product of the current element and the maximum product ending at the previous index.

Finally, we iterate through the "max_product" array and find the maximum product among all the elements. This will be the maximum product subarray.

The time complexity of this dynamic programming solution is O(n), where n is the size of the given array.