Maximum Product Subarray

Find the largest product of any subarray of an array containing positive and negative integers.

Examples

Input: array = [6, -4, -10, 1, 2]

Output: 240 (Its subarray is [6, -4, -10])

Input: array = [-2, -3, -11, 0, 61]

Output: 61 (Its subarray is [61])

Approach - 1

Follow the instructions below to write code for this problem:

The goal is to iterate over each consecutive subarray, determine the product of the elements of a particular subarray, and then return the greatest probable product from these products.

Below is the algorithmic approach to this method:

We will run a nested Python for loop to form every possible subarray of the given array
Then we will find the product of the elements of the present subarray
The function will return the maximum product value of all products calculated in the subarrays.

Here is the Python code for the algorithm mentioned above:

Code

# Python program to find the Subarray having maximum product

# Defining a function that takes the array and the length of the array and returns the maximum product of the subarray
def maxProduct(array, n):

    # Initializing the variable that will store the result
    product = array[0]

    # Iterating through the array of elements
    for i in range(n):
        prod = array[i]

        # traversing through each subarray starting with the element present at the ith position of the array
        for j in range(i + 1, n):

            # Updating the product every time so that the product variable contains only the maximum product result after all the iterations
            product = max(product, prod)
            prod *= array[j]

        # updating the product for the (n - 1)th index.
        product = max(product, prod)

    return product

# Creating an array of integers ad passing it through the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxProduct(array, n))

Output:

The maximum product of one of the subarrays is: 24156

Time Complexity: The time complexity of this approach is O(N2), where N is the number of elements in the given array.

Auxiliary Space: Since we have just created the product and the prod variable to store the product values, the program will take extra space. Hence space complexity of this problem is O(1).

Approach - 2

Below is the idea of the second approach:

The assumption made by the following method is that the given array's output will always be positive. For each of the situations mentioned above, the answer applies. It is ineffective for arrays with values of 0, 0, 0, -10, 0, 0, 0, 0, etc. This approach is readily adaptable to address negative arrays. It is analogous to the problem at hand.

The lowest (negative) result ending with the preceding number multiplied by this number might also result in the maximum product. For instance, when we reach element 3 in this sample array "12, 3, -3, -5, -7, -3," the largest product results from the multiplication of the lowest product that ends with -7 and -3.

The largest product using the procedure mentioned above is equal to one if all integers of the input array are negative. So, if the largest product is 1, we must return the largest array entry.

Below is the algorithmic approach to the idea above:

We will declare two variables, max_product, and min_product. The max_product will be initialized to 1, the variable min_product will be initialized to 1, and the variable max_ will be initialized to 0.
We will run a for loop from 0 to N.
If the current integer is greater than 0, then:
- We will set the max_product equal to min_product * array[i].
- And, we will set min_product equal to the minimum value of the min_product * array[i] and 1.
- We will set the Boolean variable as 1
Else if the integer of the current iteration is equal to zero
- We will set both the variables max_product and min_product equal to one.
Else
- We will set max_product equal to the maximum value of min_product * array[i] and 1
- We will set the variable min_product equal to max_product * array[i]
If the value of max_product is larger than that of the variable max_, then we will update max_.
If the Boolean flag is set to zero, then we will return zero
If the max_ has value one, i.e., all array integers are negative, then we will return the maximum integer in the given array
At last, we will return max_.

Here is the implementation of this approach.

Code

# Python program to find the subarray with the maximum product

# Defining a function that takes the array of integers
# This approach assumes that the array contains at least one subarray whose product is equal to 1
def maxproduct(array):

    # Finding the length of the given array
    n = len(array)

    # Maximum positive product value for the current position
    max_product = 1

    # Minimum positive product value for the current position
    min_product = 1

    # Initializing the variable that will store the maximum product so far
    max_ = 0
    flag = 0

    # Now, we will traverse through the array.
    # We will keep updating these values after each iteration
    # max_product will always be one or the positive product value of the subarray ending with array[i]
    # max_product will always be one or the negative product value of the subarray ending with array[i]
    for i in range(0, n):

        # If the element at array[i] is positive, then we will update the max_product.
        # If the element at array[i] is negative, then we will update the min_product.
        if array[i] > 0:
            max_product = max_product * array[i]
            min_product = min(min_product * array[i], 1)
            flag = 1

        # If the element at array[i] is 0, then we cannot end the maximum product here,
        # We will change the max_product and min_product values to 0
        # Reminder of the assumption: The final answer is always greater than or equal to 1.
        elif array[i] == 0:
            max_product = 1
            min_product = 1

        # If the current integer is negative, we need to perform extra steps.
        # The max_product, in this case, can either value one or have a positive value.
        # The variable min_product can either have a value of 1 or a negative value.
        # next value of the min_product will always store the previous value of max_product * array[i]
        # next value of max_product will be equal to 1 if the prev value of min_product is equal to 1, otherwise the next max_product will have the previous value of min_product * arr[i]
        else:
            t = max_product
            max_product = max(min_product * array[i], 1)
            min_product = t * array[i]
        if (max_ < max_product):
            max_ = max_product

    if flag == 0 and max_ == 0:
        return 0
    return max_

# Creating an array of integers ad passing it through the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxproduct(array))

Output:

The maximum product of one of the subarrays is: 24156

Time Complexity: The time complexity of this method is linear, i.e., O(N), where N is the number of elements in the array.

Auxiliary Space: The space complexity of this method is constant, i.e., O(1).

Efficient Approach

We will follow the algorithm below to solve the issue:

The preceding approach assumes that the provided array will always have a positive result, which is incorrect when the array solely includes negative values, such as (0, 0, -20, 0), (0, 0, 0), etc. The updated solution is comparable to the Largest Sum Contiguous Subarray Problem, which uses the largest sum.

Here is the step-by-step approach to this method:

Here we will initialize three variables called max_, max_end_here & min_end_here
For every iteration, the maximum product ending at that the index of that iteration will be a maximum of (array[i], max_end_here * array[i], min_end_here[i] * array[i])
Likewise, the minimum product ending at that index will be the minimum value of these three variables.
Hence, we will get the final maximum product value of a subarray of the given array.

Here is the implementation in Python:

Code

# Python program to find the Subarray with the maximum product

# Defining the function that will take the array of integers and the length of the array and it will return the minimum product
def maxProduct(array, n):

    # Maximum positive product end at this position
    max_end_here = array[0]

    # Minimum negative product end at this position
    min_end_here = array[0]

    # Initializing the overall maximum product value
    max_ = array[0]

    # Traversing through the input array.
    # The position at which the maximum product subarray will end will be the position of the maximum of the subarray elements,
    # The product of the current element and the maximum product value ending at the previous index, then the minimum product ending at the previous index.
    for i in range(1, n):
        t = max(max(array[i], array[i] * max_end_here),
                   array[i] * min_end_here)
        min_end_here = min(
            min(array[i], array[i] * max_end_here), array[i] * min_end_here)
        max_end_here = t
        max_ = max(max_, max_end_here)

    return max_

# Creating the array of integers and passing it to the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("Maximum product of one of the subarray is:", maxProduct(array, n))

Output:

The maximum product of one of the subarrays is: 24156

Time Complexity: The time complexity of this approach is linear since we are traversing the array of integers. Hence, the time complexity is O(N), where N is the number of elements in the array.

Auxiliary Space:This approach will take O(1) extra space since we have only created variables.

Efficient Approach

We'll use a straightforward strategy that involves traversing and multiplying the components, and if our result is higher than the product value that has already been saved, we'll store it instead. If "0" appears, set the products of all previous items to 1 since the following element will begin a new subarray.

But there is a problem with this method.

When our array contains an unusually high number of negative entries, the problem will arise. Then, to have an even number of negative integers and a positive end product, we must reject every negative component. Now that we think about subarray, we can't reject one unfavorable component. Either the initial negative component or the last negative component must be rejected.

However, only the final negative component can be discarded if we navigate from the beginning, and the initial negative component could be rejected if we navigate from the last. Therefore, we will navigate from both ends and both traversals. We will select the result from the navigation that will provide the maximum amount of product subarray.

We will reject that negative element whose rejection will give us the maximum product's subarray.

Code

# Python program to find the Subarray with the maximum product

# Defining the function that will take the array of integers and the length of the array and it will return the minimum product
def maxProduct(array, n):

    # Initializing the final product value and giving it the minimum possible value
    result = -2*10^31 - 1  
    prod = 1

    # Traversing through the input array
    # First, we will traverse in the forward direction, and then we will traverse in the reverse direction
    for i in range(n):
        prod *= array[i]

        # Updating the result value with the maximum value of the product of integers till the previous index and the product till the current index
        result = max(result, prod)  

        # If we encounter 0 in the array, we will reset the final product value to 1, as the subarray will start again from the next index. 
        if array[i] == 0:
            prod = 1  

    prod = 1

    # Traversing in the reverse direction
    for i in range(n - 1, -1, -1):
        prod *= array[i]
        result = max(result, prod)
        if array[i] == 0:
            product = 1

    return result

# Creating the array of integers and passing it to the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxProduct(array, n))

Output:

The maximum product of one of the subarrays is: 24156

Time Complexity: The time complexity of this approach is linear since we are traversing the array of integers. Hence, the time complexity is O(N), where N is the number of elements in the array.

Auxiliary Space: This approach will take O(1) extra space since we have only created variables.

Next TopicEvaluation Metrics for Machine Learning Models with Codes in Python

← prev next →

Maximum Product Subarray

Examples

Approach - 1

Approach - 2

Efficient Approach

Efficient Approach

Latest Courses

Contact info

Follow us

Tutorials

Interview Questions

Online Compiler

Python

AI, ML and Data Science

Java

B.Tech and MCA

Web Technology

Software Testing

Technical Interview

Java Interview

Web Interview

Database Interview

Company Interviews

Python Tutorial

Python OOPs

Python MySQL

Python MongoDB

Python SQLite

Python Questions

Plotly

Python Tkinter (GUI)

Python Web Blocker

Python MCQ

Related Tutorials

Python Programs

Python String functions

Python Functions

Maximum Product Subarray

Examples

Approach - 1

Approach - 2

Efficient Approach

Efficient Approach

Latest Courses

Contact info

Follow us

Tutorials

Interview Questions

Online Compiler