Find Maximum Product Subarray

In this article, we will solve the problem of finding the maximum product subarray within a given array of integers.

Problem Statement: Given an array of integers, write a function that returns the maximum product of a contiguous subarray.

Example:

Input: arr = [2, 3, -2, 4]

Output: 6

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

Solution:

To solve this problem, we need to keep track of both the maximum and minimum products up to the current position in the array. This is necessary because a negative number can change the maximum product to a minimum product and vice versa.

Here is the approach:

1.    Initialization:

• Initialize three variables: max_product, min_product, and result with the value of the first element of the array.

2.    Iteration:

• Traverse the array starting from the second element.

• For each element, calculate the maximum and minimum products up to that point.

• Update the result with the maximum of max_product and result.

3.    Update Rules:

• Update max_product as the maximum of the current element, the product of max_product and the current element, and the product of min_product and the current element.

• Update min_product as the minimum of the current element, the product of max_product and the current element, and the product of min_product and the current element.

4.    Return Result:

• Return the result, which has the maximum product subarray.

Time Complexity: O(N)

Space Complexity: O(1)