Finding Maximum Product Sub-array in a Given Array in Python

Understanding Maximum Product Sub-array

This task involves finding the contiguous sub-array that has the maximum product.

We will explore three different methods to achieve this in Python.

Method 1: Using Brute Force

This method calculates the product of all possible sub-arrays and finds the maximum.

def max_product_subarray(arr):
    max_product = float('-inf')
    for i in range(len(arr)):
        product = 1
        for j in range(i, len(arr)):
            product *= arr[j]
            max_product = max(max_product, product)
    print(f"Maximum Product: {max_product}")

arr = [2, 3, -2, 4]
max_product_subarray(arr)

Output:
Maximum Product: 6

Method 2: Using Dynamic Programming (Kadane's Variation)

This method keeps track of the maximum and minimum products at each step.

def max_product_subarray(arr):
    max_product = min_product = result = arr[0]
    for num in arr[1:]:
        temp = max(num, num * max_product, num * min_product)
        min_product = min(num, num * max_product, num * min_product)
        max_product = temp
        result = max(result, max_product)
    print(f"Maximum Product: {result}")

arr = [2, 3, -2, 4]
max_product_subarray(arr)

Output:
Maximum Product: 6

Method 3: Using a Single Pass Approach

This method efficiently finds the maximum product sub-array using a single pass.

def max_product_subarray(arr):
    max_product = min_product = result = arr[0]
    for num in arr[1:]:
        if num < 0:
            max_product, min_product = min_product, max_product
        max_product = max(num, num * max_product)
        min_product = min(num, num * min_product)
        result = max(result, max_product)
    print(f"Maximum Product: {result}")

arr = [2, 3, -2, 4]
max_product_subarray(arr)

Output:
Maximum Product: 6