C++ program for finding the maximum product of sub-array of a given array

June 2, 2022

Maximum product of sub-array in C++

Here, in this page you will find the program to find the maximum product of sub-array in C++ programming language. We are given with an array and need to find the maximum product. We will discuss two different methods in this page.

Here, we will discuss the following two methods, and compare the complexity of them,

Method 1 : Naive solution
Method 2 : Efficient solution

Let’s discuss above two methods in brief,

Method 1 :

Create a variable say result, set result = arr[0], this variable hold the required maximum product.
Run a loop for range(n)
Create a variable mul = arr[i], this variable hold the product of sub-array.
Run a inner loop, set result = max(result, mul)
And, mul *= arr[j]
Update, result = max(result, mul)
Return result.

Time and Space Complexity :

Time Complexity : O(n²)
Space Complexity : O(1)

Method 1 : C++ Code:-

Run

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = { 10, -20, -30, 0, 70, -80, -20 };
    int n=sizeof(arr)/sizeof(arr[0]);
    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 
                if(mul>result)
                result = mul;
            mul *= arr[j];
        }
        if(mul>result)
            result = mul;
    }
    
    cout<<"Maximum Product of sub-array is "<< result;
}

Output

Maximum Product of sub-array is 1600

Method 2 :

Declare variables say 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 maximum product sub-array.

Time and Space Complexity :

Time Complexity : O(n)
Space Complexity : O(1)

Method 2 : C++ Code:-

Run

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = { 1, -2, -3, 0, 7, -8, 2};
    int n=sizeof(arr)/sizeof(arr[0]);
    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];
    
    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);
        if(max_ending_here>max_so_far)
        max_so_far = max_ending_here;
    }
    
    cout<<"Maximum Product of sub-array is "<< max_so_far;
}

Output :

Maximum Product of sub-array is 7