Maximum Product Subarray - POTD | 25-July-2024

[MuhammadTausif]

Maximum Product Subarray

Link

Difficulty: Medium

Given an array arr[] that contains positive and negative integers (may contain 0 as well). Find the maximum product that we can get in a subarray of arr.

Note: It is guaranteed that the output fits in a 32-bit integer.

Examples

Input: arr[] = [-2, 6, -3, -10, 0, 2]
Output: 180
Explanation: The subarray with maximum product is {6, -3, -10} with product = 6 * (-3) * (-10) = 180.
Input: arr[] = [-1, -3, -10, 0, 60]
Output: 60
Explanation: The subarray with maximum product is {60}.
Input: arr[] = [2, 3, 4] 
Output: 24 
Explanation: For an array with all positive elements, the result is product of all elements. 

Constraints:

• 1 ≤ arr.size() ≤ 106
• -10 ≤ arr[i] ≤ 10

[MuhammadTausif]

Solved

class Solution:

    # Function to find maximum
    # product subarray
    def maxProduct(self,arr):
        # code here
        max_product = arr[0]
        min_product = arr[0]
        result = arr[0]

        # Traverse the array starting from the second element
        for i in range(1, len(arr)):
            num = arr[i]

            # If the current number is negative, swap max and min
            if num < 0:
                max_product, min_product = min_product, max_product

            # Update max_product and min_product
            max_product = max(num, max_product * num)
            min_product = min(num, min_product * num)

            # Update the result
            result = max(result, max_product)

        return result