Maximum Product Subarray

Problem Statement

The problem “Maximum Product Subarray” states that you are given an array of integer containing both positive and negative numbers. The problem statement asks to find out the maximum product of the sub-array.

Example

arr[] = { 2, -2, 3, 5}

15

Explanation

The elements in the sub-array are 3 and 5 which holds the maximum product of all the possible sub-arrays.

Algorithm

1. Traverse the array from i = 0 to less than the value n(length of the given array).
  1. Check if arr[i] is greater than 0, if true
    1. Find out the maximumRange by multiplying each value of an array to itself.
    2. Find out the minimumRange between the product of minimumRange and arr[i] and 1.
    3. Mark flag is equal to 1.
  2. If the value of the array is equal to 0, then mark the minimum and maximum range to 1.
  3. Else find out the maximum between the product of minimumRange and arr[i] and 1 and find out the minimumRange by the product value of maximumRange and arr[i].
  4. If maxValue is less than the value of the maximumRange then store the value of maximumRange to maxValue.’
2. Check if the flag is equal to 0 and also maxValue is equal to 1, then return 0
3. Return maxValue.

Explanation

We have given an array of integers. We have asked to find the maximum product that a sub-array can hold in the given array. The array is containing both the positive and negative numbers. We just have to find the maximum product here. The approach we are using here is same as the maximum length of the sub-array as the maximum sum or maximum product.

Now, we just have to focus on now the maximum product that can be made with all the possible subarrays. We will have an eye on the maximumRange and the minimumRange. In maxValue, we are going to store the maximum product here. The flag is the variable to check if we have found any positive number and also the maximum product other than 1 is present.

We are going to traverse the array from 0 to n (where n is the length of the array). We will check if arr[i] is greater than 0. If it is true, then store the product of maximumRange and arr[i] into maximumRange. Then find out the minimum value between the product of minimumRange and arr[i] and 1, and store it to minimumRange.

After that there will be another condition, if any of the array elements in the subarray is 0, then mark the minimumRange and maximumRange value to 1. Then we just have to restart from here.

If none of the conditions is satisfied. Then find out the maximum value between the product of minimumRange and the arr[i] and store it to maximumRange. The product of the maximumRange and arr[i] will be stored to the minimumRange. At each traversal, we have to compare for the greater value and update it to in maxValue and at last return the maxValue which will be holding the maximum product of all the possible subarrays.

Code

CPP code to find Maximum Product Subarray

#include<iostream>

using namespace std;

int maxSubarrayProduct(int arr[], int n)
{
    int maximumRange = 1;
    int minimumRange = 1;

    int maxValue = 1;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            maximumRange = maximumRange * arr[i];
            minimumRange = min(minimumRange * arr[i], 1);
            flag = 1;
        }
        else if (arr[i] == 0)
        {
            maximumRange = 1;
            minimumRange = 1;
        }
        else
        {
            int temp = maximumRange;
            maximumRange = max(minimumRange * arr[i], 1);
            minimumRange = temp * arr[i];
        }
        if (maxValue < maximumRange)
            maxValue = maximumRange;
    }
    if (flag == 0 && maxValue == 1)
        return 0;
    return maxValue;
}
int main()
{
    int arr[] = { 2,-2,-3,-5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "<< maxSubarrayProduct(arr, n);
    return 0;
}

Maximum Sub array product is 15

Java code to find Maximum Product Subarray

class productSubarray
{
    public static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        int maximumRange = 1;
        int minimumRange = 1;

        int maxValue = 1;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)
            {
                maximumRange = maximumRange * arr[i];
                minimumRange = Math.min(minimumRange * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0)
            {
                maximumRange = 1;
                minimumRange = 1;
            }
            else
            {
                int temp = maximumRange;
                maximumRange = Math.max(minimumRange * arr[i], 1);
                minimumRange = temp * arr[i];
            }
            if (maxValue < maximumRange)
                maxValue = maximumRange;
        }
        if (flag == 0 && maxValue == 1)
            return 0;
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,-2,-3,-5};
        System.out.println("Maximum Sub array product is "+ maxSubarrayProduct(arr));
    }
}

Maximum Sub array product is 15

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Because we ran a loop over elements in the array. The total time taken for the algorithm to run is linear.

Space Complexity

O(1) as no extra space is required. Because we have not stored data for each element. Instead of doing that we have used constant space and thus the space complexity is constant.