Maximum Product Subarray

Given an array that contains both positive and negative integers, find the product of the maximum product subarray.

Examples:

Input: arr[] = {6, -3, -10, 0, 2}
Output: 180 // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60 // The subarray is {60}

Naive Approach: To solve the problem follow the below idea:

The idea is to traverse over every contiguous subarray, find the product of each of these subarrays and return the maximum product from these results.

Follow the below steps to solve the problem:

Run a nested for loop to generate every subarray
- Calculate the product of elements in the current subarray
Return the maximum of these products calculated from the subarrays

Below is the implementation of the above approach:

C++

// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
 
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
    // Initializing result
    int result = arr[0];
 
    for (int i = 0; i < n; i++) {
        int mul = arr[i];
        // traversing in current subarray
        for (int j = i + 1; j < n; j++) {
            // updating result every time
            // to keep an eye over the maximum product
            result = max(result, mul);
            mul *= arr[j];
        }
        // updating the result for (n-1)th index.
        result = max(result, mul);
    }
    return result;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "
         << maxSubarrayProduct(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find Maximum Product Subarray
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
    // Initializing result
    int result = arr[0];
 
    for (int i = 0; i < n; i++) {
        int mul = arr[i];
        // traversing in current subarray
        for (int j = i + 1; j < n; j++) {
            // updating result every time
            // to keep an eye over the maximum product
            result = max(result, mul);
            mul *= arr[j];
        }
        // updating the result for (n-1)th index.
        result = max(result, mul);
    }
    return result;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Sub array product is %d ",
           maxSubarrayProduct(arr, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to find maximum product subarray
import java.io.*;
 
class GFG {
    /* Returns the product of max product subarray.*/
    static int maxSubarrayProduct(int arr[])
    {
        // Initializing result
        int result = arr[0];
        int n = arr.length;
 
        for (int i = 0; i < n; i++) {
            int mul = arr[i];
            // traversing in current subarray
            for (int j = i + 1; j < n; j++) {
                // updating result every time to keep an eye
                // over the maximum product
                result = Math.max(result, mul);
                mul *= arr[j];
            }
            // updating the result for (n-1)th index.
            result = Math.max(result, mul);
        }
        return result;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
        System.out.println("Maximum Sub array product is "
                           + maxSubarrayProduct(arr));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 program to find Maximum Product Subarray
 
# Returns the product of max product subarray.
 
 
def maxSubarrayProduct(arr, n):
 
    # Initializing result
    result = arr[0]
 
    for i in range(n):
 
        mul = arr[i]
 
        # traversing in current subarray
        for j in range(i + 1, n):
 
            # updating result every time
            # to keep an eye over the maximum product
            result = max(result, mul)
            mul *= arr[j]
 
        # updating the result for (n-1)th index.
        result = max(result, mul)
 
    return result
 
 
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print("Maximum Sub array product is", maxSubarrayProduct(arr, n))
 
# This code is contributed by divyeshrabadiya07

C#

// C# program to find maximum product subarray
using System;
 
class GFG {
 
    // Returns the product of max product subarray
    static int maxSubarrayProduct(int[] arr)
    {
 
        // Initializing result
        int result = arr[0];
        int n = arr.Length;
 
        for (int i = 0; i < n; i++) {
            int mul = arr[i];
 
            // Traversing in current subarray
            for (int j = i + 1; j < n; j++) {
 
                // Updating result every time
                // to keep an eye over the
                // maximum product
                result = Math.Max(result, mul);
                mul *= arr[j];
            }
 
            // Updating the result for (n-1)th index
            result = Math.Max(result, mul);
        }
        return result;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
 
        Console.Write("Maximum Sub array product is "
                      + maxSubarrayProduct(arr));
    }
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
 
// Javascript program to find Maximum Product Subarray
 
/* Returns the product of max product subarray.*/
function maxSubarrayProduct(arr, n)
{
    // Initializing result
    let result = arr[0];
 
    for (let i = 0; i < n; i++) 
    {
        let mul = arr[i];
        // traversing in current subarray
        for (let j = i + 1; j < n; j++) 
        {
            // updating result every time
            // to keep an eye over the maximum product
            result = Math.max(result, mul);
            mul *= arr[j];
        }
        // updating the result for (n-1)th index.
        result = Math.max(result, mul);
    }
    return result;
}
 
// Driver code
 
    let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
    let n = arr.length;
    document.write("Maximum Sub array product is "
        + maxSubarrayProduct(arr, n));
     
 
// This code is contributed by Mayank Tyagi
 
</script>

Output

Maximum Sub array product is 112

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below idea:

The following solution assumes that the given input array always has a positive output. The solution works for all cases mentioned above. It doesn’t work for arrays like {0, 0, -20, 0}, {0, 0, 0}.. etc. The solution can be easily modified to handle this case. It is similar to the Largest Sum Contiguous Subarray problem.

The only thing to note here is, the maximum product can also be obtained by the minimum (negative) product ending with the previous element multiplied by this element. For example, in array {12, 2, -3, -5, -6, -2}, when we are at element -2, the maximum product is the multiplication of, the minimum product ending with -6 and -2

Note: if all elements of the array are negative then the maximum product with the above algorithm is 1. so, if the maximum product is 1, then we have to return the maximum element of an array

Follow the below steps to solve the problem:

Declare two integers max_ending _here and min_ending_here equal to one and max_so_far equal to zero
Run a for loop for i [0, N]
If the current element is greater than zero
- Set max_ending_here equal to max_ending_here * arr[i]
- Set min_ending_here equal to the minimum of min_ending_here * arr[i] and 1
- Set a boolean flag equal to one
Else if the current element is equal to zero
- Set both max_ending_here and min_ending_here equal to one
Else
- Set max_ending here equal to the maximum of min_ending_here * arr[i] and 1
- Set min_ending_here equal to max_ending_here * arr[i]
If max_ending_here is greater than max_so_far then update max_so_far
If the flag is equal to zero then return zero
If the max_so_far is equal to one i.e all array elements are negative the return maximum element in the input array
Return max_so_far

Below is the implementation of the above approach:

C++

// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
 
/* Returns the product
  of max product subarray.
  */
int maxSubarrayProduct(int arr[], int n)
{
    // max positive product
    // ending at the current position
    int max_ending_here = 1;
 
    // min negative product ending
    // at the current position
    int min_ending_here = 1;
 
    // Initialize overall max product
    int max_so_far = 0;
    int flag = 0;
    /* Traverse through the array.
    Following values are
    maintained after the i'th iteration:
    max_ending_here is always 1 or
    some positive product ending with arr[i]
    min_ending_here is always 1 or
    some negative product ending with arr[i] */
    for (int i = 0; i < n; i++) {
        /* If this element is positive, update
        max_ending_here. Update min_ending_here only if
        min_ending_here is negative */
        if (arr[i] > 0) {
            max_ending_here = max_ending_here * arr[i];
            min_ending_here
                = min(min_ending_here * arr[i], 1);
            flag = 1;
        }
 
        /* If this element is 0, then the maximum product
        cannot end here, make both max_ending_here and
        min_ending_here 0
        Assumption: Output is always greater than or equal
                    to 1. */
        else if (arr[i] == 0) {
            max_ending_here = 1;
            min_ending_here = 1;
        }
 
        /* If element is negative. This is tricky
         max_ending_here can either be 1 or positive.
         min_ending_here can either be 1 or negative.
         next max_ending_here will always be prev.
         min_ending_here * arr[i] ,next min_ending_here
         will be 1 if prev max_ending_here is 1, otherwise
         next min_ending_here will be prev max_ending_here *
         arr[i] */
 
        else {
            int temp = max_ending_here;
            max_ending_here
                = max(min_ending_here * arr[i], 1);
            min_ending_here = temp * arr[i];
        }
 
        // update max_so_far, if needed
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    if (flag == 0 && max_so_far == 0)
        return 0;
    /* if all the array elements are negative */
    if (max_so_far == 1) {
        max_so_far = arr[0];
        for (int i = 1; i < n; i++)
            max_so_far = max(max_so_far, arr[i]);
    }
    return max_so_far;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "
         << maxSubarrayProduct(arr, n);
    return 0;
}
 
// This is code is contributed by rathbhupendra

C

// C program to find Maximum Product Subarray
#include <stdio.h>
 
// Utility functions to get minimum of two integers
int min(int x, int y) { return x < y ? x : y; }
 
// Utility functions to get maximum of two integers
int max(int x, int y) { return x > y ? x : y; }
 
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
int maxSubarrayProduct(int arr[], int n)
{
    // max positive product
    // ending at the current position
    int max_ending_here = 1;
 
    // min negative product ending
    // at the current position
    int min_ending_here = 1;
 
    // Initialize overall max product
    int max_so_far = 0;
    int flag = 0;
 
    /* Traverse through the array. Following values are
    maintained after the i'th iteration:
    max_ending_here is always 1 or some positive product
                    ending with arr[i]
    min_ending_here is always 1 or some negative product
                    ending with arr[i] */
    for (int i = 0; i < n; i++) {
        /* If this element is positive, update
        max_ending_here. Update min_ending_here only if
        min_ending_here is negative */
        if (arr[i] > 0) {
            max_ending_here = max_ending_here * arr[i];
            min_ending_here
                = min(min_ending_here * arr[i], 1);
            flag = 1;
        }
 
        /* If this element is 0, then the maximum product
        cannot end here, make both max_ending_here and
        min_ending_here 0
        Assumption: Output is alway greater than or equal
                    to 1. */
        else if (arr[i] == 0) {
            max_ending_here = 1;
            min_ending_here = 1;
        }
 
        /* If element is negative. This is tricky
        max_ending_here can either be 1 or positive.
        min_ending_here can either be 1 or negative.
        next min_ending_here will always be prev.
        max_ending_here * arr[i] next max_ending_here
        will be 1 if prev min_ending_here is 1, otherwise
        next max_ending_here will be prev min_ending_here *
        arr[i] */
        else {
            int temp = max_ending_here;
            max_ending_here
                = max(min_ending_here * arr[i], 1);
            min_ending_here = temp * arr[i];
        }
 
        // update max_so_far, if needed
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    if (flag == 0 && max_so_far == 0)
        return 0;
    return max_so_far;
 
    return max_so_far;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Sub array product is %d",
           maxSubarrayProduct(arr, n));
    return 0;
}

Java

// Java program to find maximum product subarray
import java.io.*;
 
class ProductSubarray {
 
    // Utility functions to get
    // minimum of two integers
    static int min(int x, int y) { return x < y ? x : y; }
 
    // Utility functions to get
    // maximum of two integers
    static int max(int x, int y) { return x > y ? x : y; }
 
    /* Returns the product of
    max product subarray.
    Assumes that the given
    array always has a subarray
    with product more than 1 */
    static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        // max positive product
        // ending at the current
        // position
        int max_ending_here = 1;
 
        // min negative product
        // ending at the current
        // position
        int min_ending_here = 1;
 
        // Initialize overall max product
        int max_so_far = 0;
        int flag = 0;
 
        /* Traverse through the array. Following
        values are maintained after the ith iteration:
        max_ending_here is always 1 or some positive product
                        ending with arr[i]
        min_ending_here is always 1 or some negative product
                        ending with arr[i] */
        for (int i = 0; i < n; i++) {
            /* If this element is positive, update
               max_ending_here. Update min_ending_here only
               if min_ending_here is negative */
            if (arr[i] > 0) {
                max_ending_here = max_ending_here * arr[i];
                min_ending_here
                    = min(min_ending_here * arr[i], 1);
                flag = 1;
            }
 
            /* If this element is 0, then the maximum
            product cannot end here, make both
            max_ending_here and min_ending _here 0
            Assumption: Output is always greater than or
            equal to 1. */
            else if (arr[i] == 0) {
                max_ending_here = 1;
                min_ending_here = 1;
            }
 
            /* If element is negative. This is tricky
            max_ending_here can either be 1 or positive.
            min_ending_here can either be 1 or negative.
            next min_ending_here will always be prev.
            max_ending_here * arr[i]
            next max_ending_here will be 1 if prev
            min_ending_here is 1, otherwise
            next max_ending_here will be
                        prev min_ending_here * arr[i] */
            else {
                int temp = max_ending_here;
                max_ending_here
                    = max(min_ending_here * arr[i], 1);
                min_ending_here = temp * arr[i];
            }
 
            // update max_so_far, if needed
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
 
        if (flag == 0 && max_so_far == 0)
            return 0;
        return max_so_far;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
        System.out.println("Maximum Sub array product is "
                           + maxSubarrayProduct(arr));
    }
} /*This code is contributed by Devesh Agrawal*/

Python3

# Python program to find maximum product subarray
 
# Returns the product of max product subarray.
# Assumes that the given array always has a subarray
# with product more than 1
 
 
def maxsubarrayproduct(arr):
 
    n = len(arr)
 
    # max positive product ending at the current position
    max_ending_here = 1
 
    # min positive product ending at the current position
    min_ending_here = 1
 
    # Initialize maximum so far
    max_so_far = 0
    flag = 0
 
    # Traverse throughout the array. Following values
    # are maintained after the ith iteration:
    # max_ending_here is always 1 or some positive product
    # ending with arr[i]
    # min_ending_here is always 1 or some negative product
    # ending with arr[i]
    for i in range(0, n):
 
        # If this element is positive, update max_ending_here.
        # Update min_ending_here only if min_ending_here is
        # negative
        if arr[i] > 0:
            max_ending_here = max_ending_here * arr[i]
            min_ending_here = min(min_ending_here * arr[i], 1)
            flag = 1
 
        # If this element is 0, then the maximum product cannot
        # end here, make both max_ending_here and min_ending_here 0
        # Assumption: Output is alway greater than or equal to 1.
        elif arr[i] == 0:
            max_ending_here = 1
            min_ending_here = 1
 
        # If element is negative. This is tricky
        # max_ending_here can either be 1 or positive.
        # min_ending_here can either be 1 or negative.
        # next min_ending_here will always be prev.
        # max_ending_here * arr[i]
        # next max_ending_here will be 1 if prev
        # min_ending_here is 1, otherwise
        # next max_ending_here will be prev min_ending_here * arr[i]
        else:
            temp = max_ending_here
            max_ending_here = max(min_ending_here * arr[i], 1)
            min_ending_here = temp * arr[i]
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here
 
    if flag == 0 and max_so_far == 0:
        return 0
    return max_so_far
 
 
# Driver function to test above function
arr = [1, -2, -3, 0, 7, -8, -2]
print("Maximum product subarray is", maxsubarrayproduct(arr))
 
# This code is contributed by Devesh Agrawal

C#

// C# program to find maximum product subarray
using System;
 
class GFG {
 
    // Utility functions to get minimum of two integers
    static int min(int x, int y) { return x < y ? x : y; }
 
    // Utility functions to get maximum of two integers
    static int max(int x, int y) { return x > y ? x : y; }
 
    /* Returns the product of max product subarray.
    Assumes that the given array always has a subarray
    with product more than 1 */
    static int maxSubarrayProduct(int[] arr)
    {
        int n = arr.Length;
        // max positive product ending at the current
        // position
        int max_ending_here = 1;
 
        // min negative product ending at the current
        // position
        int min_ending_here = 1;
 
        // Initialize overall max product
        int max_so_far = 0;
        int flag = 0;
 
        /* Traverse through the array. Following
        values are maintained after the ith iteration:
        max_ending_here is always 1 or some positive
        product ending with arr[i] min_ending_here is
        always 1 or some negative product ending
        with arr[i] */
        for (int i = 0; i < n; i++) {
            /* If this element is positive, update
            max_ending_here. Update min_ending_here
            only if min_ending_here is negative */
            if (arr[i] > 0) {
                max_ending_here = max_ending_here * arr[i];
                min_ending_here
                    = min(min_ending_here * arr[i], 1);
                flag = 1;
            }
 
            /* If this element is 0, then the maximum
            product cannot end here, make both
            max_ending_here and min_ending_here 0
            Assumption: Output is alway greater than or
            equal to 1. */
            else if (arr[i] == 0) {
                max_ending_here = 1;
                min_ending_here = 1;
            }
 
            /* If element is negative. This is tricky
            max_ending_here can either be 1 or positive.
            min_ending_here can either be 1 or negative.
            next min_ending_here will always be prev.
            max_ending_here * arr[i]
            next max_ending_here will be 1 if prev
            min_ending_here is 1, otherwise
            next max_ending_here will be
            prev min_ending_here * arr[i] */
            else {
                int temp = max_ending_here;
                max_ending_here
                    = max(min_ending_here * arr[i], 1);
                min_ending_here = temp * arr[i];
            }
 
            // update max_so_far, if needed
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
 
        if (flag == 0 && max_so_far == 0)
            return 0;
 
        return max_so_far;
    }
 
    // Driver Code
    public static void Main()
    {
 
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
 
        Console.WriteLine("Maximum Sub array product is "
                          + maxSubarrayProduct(arr));
    }
}
 
/*This code is contributed by vt_m*/

Javascript

<script>
 
// JavaScript program to find 
// Maximum Product Subarray
 
/* Returns the product 
  of max product subarray.
Assumes that the given 
array always has a subarray
with product more than 1 */
function maxSubarrayProduct(arr, n)
{
    // max positive product 
    // ending at the current position
    let max_ending_here = 1;
 
    // min negative product ending 
    // at the current position
    let min_ending_here = 1;
 
    // Initialize overall max product
    let max_so_far = 0;
    let flag = 0;
    /* Traverse through the array. 
    Following values are
    maintained after the i'th iteration:
    max_ending_here is always 1 or 
    some positive product ending with arr[i]
    min_ending_here is always 1 or 
    some negative product ending with arr[i] */
    for (let i = 0; i < n; i++)
    {
        /* If this element is positive, update
        max_ending_here. Update min_ending_here only if
        min_ending_here is negative */
        if (arr[i] > 0) 
        {
            max_ending_here = max_ending_here * arr[i];
            min_ending_here
                = Math.min(min_ending_here * arr[i], 1);
            flag = 1;
        }
 
        /* If this element is 0, then the maximum product
        cannot end here, make both max_ending_here and
        min_ending_here 0
        Assumption: Output is always greater than or equal
                    to 1. */
        else if (arr[i] == 0) {
            max_ending_here = 1;
            min_ending_here = 1;
        }
 
        /* If element is negative. This is tricky
         max_ending_here can either be 1 or positive.
         min_ending_here can either be 1 or negative.
         next max_ending_here will always be prev.
         min_ending_here * arr[i] ,next min_ending_here
         will be 1 if prev max_ending_here is 1, otherwise
         next min_ending_here will be prev max_ending_here *
         arr[i] */
 
        else {
            let temp = max_ending_here;
            max_ending_here
                = Math.max(min_ending_here * arr[i], 1);
            min_ending_here = temp * arr[i];
        }
 
        // update max_so_far, if needed
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    if (flag == 0 && max_so_far == 0)
        return 0;
    return max_so_far;
}
 
 
    // Driver program 
     
    let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
    let n = arr.length;
    document.write("Maximum Sub array product is " + 
                    maxSubarrayProduct(arr,n)); 
     
</script>

PHP

<?php
// php program to find Maximum Product
// Subarray
 
// Utility functions to get minimum of
// two integers
function minn ($x, $y) 
{
    return $x < $y? $x : $y;
}
 
// Utility functions to get maximum of
// two integers
function maxx ($x, $y) 
{
    return $x > $y? $x : $y; 
}
 
/* Returns the product of max product
subarray. Assumes that the given array
always has a subarray with product
more than 1 */
function maxSubarrayProduct($arr, $n)
{
     
    // max positive product ending at 
    // the current position
    $max_ending_here = 1;
 
    // min negative product ending at
    // the current position
    $min_ending_here = 1;
 
    // Initialize overall max product
    $max_so_far = 0;
    $flag = 0;
 
    /* Traverse through the array.
    Following values are maintained 
    after the i'th iteration: 
    max_ending_here is always 1 or
    some positive product ending with
    arr[i] min_ending_here is always
    1 or some negative product ending
    with arr[i] */
    for ($i = 0; $i < $n; $i++)
    {
         
        /* If this element is positive,
        update max_ending_here. Update
        min_ending_here only if 
        min_ending_here is negative */
        if ($arr[$i] > 0)
        {
            $max_ending_here = 
            $max_ending_here * $arr[$i];
             
            $min_ending_here = 
                min ($min_ending_here
                        * $arr[$i], 1);
            $flag = 1;
        }
 
        /* If this element is 0, then the
        maximum product cannot end here,
        make both max_ending_here and 
        min_ending_here 0
        Assumption: Output is alway 
        greater than or equal to 1. */
        else if ($arr[$i] == 0)
        {
            $max_ending_here = 1;
            $min_ending_here = 1;
        }
 
        /* If element is negative. This
        is tricky max_ending_here can
        either be 1 or positive. 
        min_ending_here can either be 1 or
        negative. next min_ending_here will
        always be prev. max_ending_here * 
        arr[i] next max_ending_here will be
        1 if prev min_ending_here is 1,
        otherwise next max_ending_here will
        be prev min_ending_here * arr[i] */
        else
        {
            $temp = $max_ending_here;
            $max_ending_here =
                max ($min_ending_here
                        * $arr[$i], 1);
                             
            $min_ending_here =
                        $temp * $arr[$i];
        }
 
        // update max_so_far, if needed
        if ($max_so_far < $max_ending_here)
            $max_so_far = $max_ending_here;
    }
 
    if($flag==0 && $max_so_far==0) return 0; 
    return $max_so_far;
}
 
// Driver Program to test above function
    $arr = array(1, -2, -3, 0, 7, -8, -2);
    $n = 7;
    echo("Maximum Sub array product is ");
    echo (maxSubarrayProduct($arr, $n));
 
// This code is contributed by nitin mittal 
?>

Output

Maximum Sub array product is 112

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below idea:

The above solution assumes there is always a positive outcome for the given array which does not work for cases where the array contains only non-positive elements like {0, 0, -20, 0}, {0, 0, 0}.. etc. The modified solution is also similar to the Largest Sum Contiguous Subarray problem which uses Kadane’s algorithm.

Follow the below steps to solve the problem:

Here we use 3 variables called max_so_far, max_ending_here & min_ending_here
For every index, the maximum number ending at that index will be the maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
Similarly, the minimum number ending here will be the minimum of these 3
Thus we get the final value for the maximum product subarray

Below is the implementation of the above approach:

C++

// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
 
/* Returns the product
of max product subarray. */
int maxSubarrayProduct(int arr[], int n)
{
    // max positive product
    // ending at the current position
    int max_ending_here = arr[0];
 
    // min negative product ending
    // at the current position
    int min_ending_here = arr[0];
 
    // Initialize overall max product
    int max_so_far = arr[0];
    /* Traverse through the array.
    the maximum product subarray ending at an index
    will be the maximum of the element itself,
    the product of element and max product ending previously
    and the min product ending previously. */
    for (int i = 1; i < n; i++) {
        int temp = max({ arr[i], arr[i] * max_ending_here,
                         arr[i] * min_ending_here });
        min_ending_here
            = min({ arr[i], arr[i] * max_ending_here,
                    arr[i] * min_ending_here });
        max_ending_here = temp;
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "
         << maxSubarrayProduct(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find Maximum Product Subarray
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// Find minimum between two numbers.
int min(int num1, int num2)
{
    return (num1 > num2) ? num2 : num1;
}
 
/* Returns the product of max product subarray. */
int maxSubarrayProduct(int arr[], int n)
{
    // max positive product
    // ending at the current position
    int max_ending_here = arr[0];
 
    // min negative product ending
    // at the current position
    int min_ending_here = arr[0];
 
    // Initialize overall max product
    int max_so_far = arr[0];
    /* Traverse through the array.
    the maximum product subarray ending at an index
    will be the maximum of the element itself,
    the product of element and max product ending previously
    and the min product ending previously. */
    for (int i = 1; i < n; i++) {
        int temp
            = max(max(arr[i], arr[i] * max_ending_here),
                  arr[i] * min_ending_here);
        min_ending_here
            = min(min(arr[i], arr[i] * max_ending_here),
                  arr[i] * min_ending_here);
        max_ending_here = temp;
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Sub array product is %d",
           maxSubarrayProduct(arr, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
    // Java program to find Maximum Product Subarray
 
    // Returns the product
    // of max product subarray.
    static int maxSubarrayProduct(int arr[], int n)
    {
 
        // max positive product
        // ending at the current position
        int max_ending_here = arr[0];
 
        // min negative product ending
        // at the current position
        int min_ending_here = arr[0];
 
        // Initialize overall max product
        int max_so_far = arr[0];
 
        // /* Traverse through the array.
        // the maximum product subarray ending at an index
        // will be the maximum of the element itself,
        // the product of element and max product ending
        // previously and the min product ending previously.
        // */
        for (int i = 1; i < n; i++) {
            int temp = Math.max(
                Math.max(arr[i], arr[i] * max_ending_here),
                arr[i] * min_ending_here);
            min_ending_here = Math.min(
                Math.min(arr[i], arr[i] * max_ending_here),
                arr[i] * min_ending_here);
            max_ending_here = temp;
            max_so_far
                = Math.max(max_so_far, max_ending_here);
        }
 
        return max_so_far;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
        int n = arr.length;
        System.out.printf("Maximum Sub array product is %d",
                          maxSubarrayProduct(arr, n));
    }
}
 
// This code is contributed by shinjanpatra

Python3

# Python3 program to find Maximum Product Subarray
 
#  Returns the product
# of max product subarray.
 
 
def maxSubarrayProduct(arr, n):
 
    # max positive product
    # ending at the current position
    max_ending_here = arr[0]
 
    # min negative product ending
    # at the current position
    min_ending_here = arr[0]
 
    # Initialize overall max product
    max_so_far = arr[0]
 
    # /* Traverse through the array.
    # the maximum product subarray ending at an index
    # will be the maximum of the element itself,
    # the product of element and max product ending previously
    # and the min product ending previously. */
    for i in range(1, n):
        temp = max(max(arr[i], arr[i] * max_ending_here),
                   arr[i] * min_ending_here)
        min_ending_here = min(
            min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here)
        max_ending_here = temp
        max_so_far = max(max_so_far, max_ending_here)
 
    return max_so_far
 
 
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print(f"Maximum Sub array product is {maxSubarrayProduct(arr, n)}")
 
# This code is contributed by shinjanpatra

C#

// C# program to find maximum product subarray
using System;
 
class GFG {
 
    /* Returns the product of max product subarray.
    Assumes that the given array always has a subarray
    with product more than 1 */
    static int maxSubarrayProduct(int[] arr)
    {
        // max positive product
        // ending at the current position
        int max_ending_here = arr[0];
 
        // min negative product ending
        // at the current position
        int min_ending_here = arr[0];
 
        // Initialize overall max product
        int max_so_far = arr[0];
        /* Traverse through the array.
        the maximum product subarray ending at an index
        will be the maximum of the element itself,
        the product of element and max product ending
        previously and the min product ending previously. */
        for (int i = 1; i < arr.Length; i++) {
            int temp = Math.Max(
                Math.Max(arr[i], arr[i] * max_ending_here),
                arr[i] * min_ending_here);
            min_ending_here = Math.Min(
                Math.Min(arr[i], arr[i] * max_ending_here),
                arr[i] * min_ending_here);
            max_ending_here = temp;
            max_so_far
                = Math.Max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
 
    // Driver Code
    public static void Main()
    {
 
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
 
        Console.WriteLine("Maximum Sub array product is "
                          + maxSubarrayProduct(arr));
    }
}
 
// This code is contributed by CodeWithMini

Javascript

<script>
 
// JavaScript program to find Maximum Product Subarray
 
/* Returns the product
of max product subarray. */
function maxSubarrayProduct(arr, n)
{
 
    // max positive product
    // ending at the current position
    let max_ending_here = arr[0];
 
    // min negative product ending
    // at the current position
    let min_ending_here = arr[0];
 
    // Initialize overall max product
    let max_so_far = arr[0];
     
    /* Traverse through the array.
    the maximum product subarray ending at an index
    will be the maximum of the element itself,
    the product of element and max product ending previously
    and the min product ending previously. */
    for (let i = 1; i < n; i++)
    {
        let temp = Math.max(Math.max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
        min_ending_here = Math.min(Math.min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
        max_ending_here = temp;
        max_so_far = Math.max(max_so_far, max_ending_here);
    }
    return max_so_far;
}
 
// Driver code
let arr = [ 1, -2, -3, 0, 7, -8, -2 ]
let n = arr.length
document.write("Maximum Sub array product is "+maxSubarrayProduct(arr, n));
 
// This code is contributed by shinjanpatra
 
</script>

Output

Maximum Sub array product is 112

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach: Using traversal from starting and end of an array

We will follow a simple approach that is to traverse and multiply elements and if our value is greater than the previously stored value then store this value in place of the previously stored value. If we encounter “0” then make products of all elements till now equal to 1 because from the next element, we will start a new subarray.

But what can be the problem with that?

Problem will occur when our array will contain odd no. of negative elements. In that case, we have to reject anyone negative element so that we can even no. of negative elements and their product can be positive. Now since we are considering subarray so we can’t simply reject any one negative element. We have to either reject the first negative element or the last negative element.

But if we will traverse from starting then only the last negative element can be rejected and if we traverse from the last then the first negative element can be rejected. So we will traverse from both the end and from both the traversal we will take answer from that traversal only which will give maximum product subarray.

So actually we will reject that negative element whose rejection will give us the maximum product’s subarray.

Code-

C++

// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
 
/* Returns the product
of max product subarray. */
long long int maxSubarrayProduct(int arr[], int n)
{
   long long ans=INT_MIN;
   long long product=1;
    
   for(int i=0;i<n;i++){
       product*=arr[i];
       ans=max(ans,product);
       if(arr[i]==0){product=1;}
   }
    
   product=1;
    
   for(int i=n-1;i>=0;i--){
       product*=arr[i];
       ans=max(ans,product);
       if(arr[i]==0){product=1;}
   }
   return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "
         << maxSubarrayProduct(arr, n);
    return 0;
}

Java

// Java program to find Maximum Product Subarray
import java.util.*;
 
public class Main {
    /* Returns the product of max product subarray. */
    public static long maxSubarrayProduct(int[] arr, int n)
    {
        long ans = Integer.MIN_VALUE;
        long product = 1;
        // Traverse the array from left to right
        for (int i = 0; i < n; i++) {
            product *= arr[i];
            ans = Math.max(ans, product);
            if (arr[i] == 0) {
                product = 1;
            }
        }
 
        product = 1;
 
        // Traverse the array from right to left
        for (int i = n - 1; i >= 0; i--) {
            product *= arr[i];
            ans = Math.max(ans, product);
            if (arr[i] == 0) {
                product = 1;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
        int n = arr.length;
        System.out.println("Maximum Subarray product is "
                           + maxSubarrayProduct(arr, n));
    }
}

Python3

# Python program to find Maximum Product Subarray
 
import sys
 
# Returns the product of max product subarray.
def maxSubarrayProduct(arr, n):
    ans = -sys.maxsize - 1  # Initialize the answer to the minimum possible value
    product = 1
 
    for i in range(n):
        product *= arr[i]
        ans = max(ans, product)  # Update the answer with the maximum of the current answer and product
        if arr[i] == 0:
            product = 1  # Reset the product to 1 if the current element is 0
 
    product = 1
 
    for i in range(n - 1, -1, -1):
        product *= arr[i]
        ans = max(ans, product)
        if arr[i] == 0:
            product = 1
 
    return ans
 
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print("Maximum Subarray product is", maxSubarrayProduct(arr, n))

C#

using System;
 
public class MainClass {
    // Returns the product of max product subarray.
    public static int MaxSubarrayProduct(int[] arr, int n)
    {
        int ans
            = int.MinValue; // Initialize the answer to the
                            // minimum possible value
        int product = 1;
 
        for (int i = 0; i < n; i++) {
            product *= arr[i];
            ans = Math.Max(
                ans, product); // Update the answer with the
                               // maximum of the current
                               // answer and product
            if (arr[i] == 0) {
                product = 1; // Reset the product to 1 if
                             // the current element is 0
            }
        }
 
        product = 1;
 
        for (int i = n - 1; i >= 0; i--) {
            product *= arr[i];
            ans = Math.Max(ans, product);
            if (arr[i] == 0) {
                product = 1;
            }
        }
 
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
        int n = arr.Length;
        Console.WriteLine("Maximum Subarray product is "
                          + MaxSubarrayProduct(arr, n));
    }
}

Javascript

// JavaScript program to find Maximum Product Subarray
 
// Function to find the maximum product subarray
function maxSubarrayProduct(arr, n) {
  let ans = -Infinity;
  let product = 1;
 
  for (let i = 0; i < n; i++) {
    product *= arr[i];
    ans = Math.max(ans, product);
    if (arr[i] === 0) {
      product = 1;
    }
  }
 
  product = 1;
 
  for (let i = n - 1; i >= 0; i--) {
    product *= arr[i];
    ans = Math.max(ans, product);
    if (arr[i] === 0) {
      product = 1;
    }
  }
 
  return ans;
}
 
// Driver code
const arr = [1, -2, -3, 0, 7, -8, -2];
const n = arr.length;
console.log(`Maximum Subarray product is ${maxSubarrayProduct(arr, n)}`);
 
//This code is written by Sundaram

Output

Maximum Sub array product is 112

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below idea:

The code defines a function named maxSubarrayProduct that takes an integer array A and its size n as arguments.
It initializes a variable r with the first element of the array A. This variable will store the maximum subarray product found so far.
The function then enters a loop that starts from the second element of the array A and goes up to the last element.
Inside the loop, the function initializes two variables imax and imin with the value of r. These variables will store the maximum and minimum product of subarrays that end with the current number A[i].
If the current number A[i] is negative, the function swaps imax and imin. This is because multiplying a negative number with a maximum product will give a minimum product and vice versa.
The function then calculates the maximum and minimum product of subarrays that end with the current number A[i]. It does this by taking the maximum and minimum of either the current number A[i] or the maximum and minimum product of subarrays that end with the previous number times the current number.
The function then updates the value of r to the maximum of r and imax. This is because the newly computed maximum value is a candidate for the global maximum subarray product.
After the loop ends, the function returns the value of r.
The code defines a main function that initializes an array arr with some values, calls the maxSubarrayProduct function passing the array and its size as arguments, and then prints the result to the console.
The program then exits with a status of 0.

Below is the implementation of the above approach:

C++

#include <iostream>
using namespace std;
 
int maxSubarrayProduct(int A[], int n) {
    // store the result that is the max we have found so far
    int r = A[0];
 
    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        // multiplied by a negative makes big number smaller, small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0)
            swap(imax, imin);
 
        // max/min product for the current number is either the current number itself
        // or the max/min by the previous number times the current one
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);
 
        // the newly computed max value is a candidate for our global result
        r = max(r, imax);
    }
    return r;
}
 
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Subarray Product is "
         << maxSubarrayProduct(arr, n);
    return 0;
}

Java

import java.util.*;
 
public class Main {
    public static int maxSubarrayProduct(int[] A, int n) {
        // store the result that is the max we have found so far
        int r = A[0];
 
        // imax/imin stores the max/min product of
        // subarray that ends with the current number A[i]
        int imax = r, imin = r;
        for (int i = 1; i < n; i++) {
            // multiplied by a negative makes big number smaller, 
           // small number bigger
           // so we redefine the extremums by swapping them
            if (A[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
 
            // max/min product for the current number is either the current number itself
            // or the max/min by the previous number times the current one
            imax = Math.max(A[i], imax * A[i]);
            imin = Math.min(A[i], imin * A[i]);
 
            // the newly computed max value is a candidate for our global result
            r = Math.max(r, imax);
        }
        return r;
    }
 
    public static void main(String[] args) {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
        int n = arr.length;
        System.out.println("Maximum Subarray Product is " + maxSubarrayProduct(arr, n));
    }
}

Python3

def maxSubarrayProduct(arr):
    # Store the result that is the max we have found so far
    r = arr[0]
 
    # imax/imin store the max/min product of subarray that ends 
    # with the current number arr[i]
    imax = r
    imin = r
 
    for i in range(1, len(arr)):
        # Multiplied by a negative makes a big 
        # number smaller and a small number bigger
        # So we redefine the extremums by swapping them
        if arr[i] < 0:
            imax, imin = imin, imax
 
        # Max/min product for the current number is 
        # either the current number itself
        # or the max/min by the previous number times the current one
        imax = max(arr[i], imax * arr[i])
        imin = min(arr[i], imin * arr[i])
 
        # The newly computed max value is a candidate 
        # for our global result
        r = max(r, imax)
 
    return r
 
arr = [1, -2, -3, 0, 7, -8, -2]
print("Maximum Subarray Product is", maxSubarrayProduct(arr))

C#

using System;
 
class Program {
 
    // Function to find the maximum subarray
    // product from the given array
    static int MaxSubarrayProduct(int[] arr, int n)
    {
        int r = arr[0];
        int imax = r, imin = r;
 
        for (int i = 1; i < n; i++) {
            if (arr[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
 
            // Update the minimum and maximum
            imax = Math.Max(arr[i], imax * arr[i]);
            imin = Math.Min(arr[i], imin * arr[i]);
 
            r = Math.Max(r, imax);
        }
 
        return r;
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
        int n = arr.Length;
 
        Console.WriteLine("Maximum Subarray Product is {0}",
                          MaxSubarrayProduct(arr, n));
    }
}

Javascript

// Function to find the maximum subarray
// product from the given array
function maxSubarrayProduct(A, n) {
    // store the result that is the max we have found so far
    let r = A[0];
 
    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    let imax = r;
    let imin = r;
 
    for (let i = 1; i < n; i++) {
        // multiplied by a negative makes big number smaller, 
        // small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0) {
            [imax, imin] = [imin, imax];
        }
 
        // max/min product for the current number is either 
        // the current number itself
        // or the max/min by the previous number times the 
        // current one
        imax = Math.max(A[i], imax * A[i]);
        imin = Math.min(A[i], imin * A[i]);
 
        // the newly computed max value is a candidate for 
        // our global result
        r = Math.max(r, imax);
    }
 
    return r;
}
 
const arr = [1, -2, -3, 0, 7, -8, -2];
const n = arr.length;
 
console.log("Maximum Subarray Product is " + maxSubarrayProduct(arr, n));

Output

Maximum Subarray Product is 112

Time Complexity: O(n)

Auxiliary Space: O(1)

This article is compiled by Dheeraj Jain and reviewed by neveropen team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Maximum Product Subarray

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

PHP

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US