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

November 5, 2021

Maximum product of sub-array

Program to find the maximum product sub array in a given array is discussed here. Given an array of integers as input, the task is to find the sub array from the given input array whose product is maximum.

Example

Input: {-1, -3, -10, 60,0}

Output: 1800

Sub-array : {-3, -10, 60}

Product of the sub-array = -3 * -10 * 60 = 1800

maximum-product-of-subarray

Algorithm

  1. take array as input
  2. initialize max_ending_here=1 ,min_ending_here=1, max_so_for=0, flag=0
  3. traverse the array from start to end
    1. If arr[i] > 0,
      1. max_ending_here = max_ending_here*arr[i] .
      2. min_ending_here=min(min_ending_here*arr[i],1)
    2. If arr[i] == 0,
      1. max_ending_here =1
      2. min_ending_here=1
    3. If arr[i] < 0,
      1. temp=max_ending_here
      2. max_ending_here =max(min_ending_here*arr[i] , 1)
      3. min_ending_here=temp* arr[i]
    4. max_so_far= max(max_so_far,max_ending_here)
  4. print(max_so_for)

C++ Code:-

    
    // C++ program to find Maximum Product Subarray
    #include <bits/stdc++.h>
    using namespace std;

    int maxSubarrayProduct(int arr[], int n{
        int max_ending_here = 1;
        int min_ending_here = 1;
        int max_so_far = 0;
        int flag = 0;

        for (int i = 0; i < n; i++){
            if (arr[i] > 0) {
                max_ending_here = max_ending_here * arr[i];
                min_ending_here
                    = min(min_ending_here * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0) {
                max_ending_here = 1;
                min_ending_here = 1;
            }
            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;
    }

    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;
    }


 

    
    Output:-
    Maximum Sub array product is 112