Python - Find the Maximum Product Subarray in an Array

Python – Find the Maximum Product Subarray in an Array

In this tutorial, we will learn how to solve the problem of finding the maximum product subarray in an array. This problem is popular in data structures and algorithms (DSA) interviews. We will explain the concept step by step, provide sample inputs and outputs, and conclude with a complete Python program.

Problem Statement

Given an array of integers, which may include negative numbers and zeros, your task is to find the contiguous subarray (containing at least one number) that has the largest product. The challenge lies in handling negative numbers, as multiplying two negatives can result in a positive product.

Sample Input and Output

Example 1:

</>

Copy

Input: arr = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] gives the maximum product 6.

Example 2:

</>

Copy

Input: arr = [-2, 0, -1]
Output: 0
Explanation: The subarray [0] gives the maximum product 0.

Solution Approach

To solve this problem, we use a dynamic programming approach by maintaining two variables at each iteration:

max_so_far: The maximum product ending at the current index.
min_so_far: The minimum product ending at the current index. This is important because a negative number multiplied by a negative product can turn into a large positive product.

At each element in the array, we consider three possibilities:

The current element itself.
The product of the current element and the previous max_so_far.
The product of the current element and the previous min_so_far.

If the current element is negative, we swap max_so_far and min_so_far before updating them, because multiplying by a negative reverses the sign. Finally, we update our result with the maximum product encountered during the iteration.

Python Program

</>

Copy

def max_product_subarray(arr):
    # Edge case: if the array is empty, return 0
    if not arr:
        return 0

    # Initialize max_so_far, min_so_far, and result with the first element
    max_so_far = min_so_far = result = arr[0]

    # Iterate through the array starting from the second element
    for num in arr[1:]:
        # If current number is negative, swap max_so_far and min_so_far
        if num < 0:
            max_so_far, min_so_far = min_so_far, max_so_far

        # Update max_so_far and min_so_far
        max_so_far = max(num, max_so_far * num)
        min_so_far = min(num, min_so_far * num)

        # Update the result with the highest product found so far
        result = max(result, max_so_far)

    return result

# Sample Input 1
arr1 = [2, 3, -2, 4]
print("Maximum Product Subarray (Example 1):", max_product_subarray(arr1))

# Sample Input 2
arr2 = [-2, 0, -1]
print("Maximum Product Subarray (Example 2):", max_product_subarray(arr2))

Conclusion

This tutorial explained how to find the maximum product subarray in an array using a dynamic programming approach. By maintaining both maximum and minimum products at each step and carefully handling negative numbers, we can efficiently determine the subarray with the largest product.

TutorialKart

Python – Find the Maximum Product Subarray in an Array