Finding the maximum product of a subarray in an array




Maximum product sub-array implementation

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int MaxProduct_SubArray (vector<int>& vec) {

    int max_sum_sofar = vec[0];
    int max_ending_here = vec[0];
    int min_ending_here = vec[0];

    for (int i=1; i<vec.size(); i++) {
        
        int current_max = max({vec[i],
                               vec[i]*max_ending_here,
                               vec[i]*min_ending_here});

        int current_min = min({vec[i],
                               vec[i]*max_ending_here,
                               vec[i]*min_ending_here});

        max_ending_here = current_max;
        min_ending_here = current_min;

        max_sum_sofar = max(max_sum_sofar, max_ending_here);
    }
    return max_sum_sofar;
}

void Display (vector<int>& vec) {
    cout << "Array : ";
    for (const auto& n :vec ) {
        cout << n << " ";
    } cout << endl;
}

int main() {

    vector<int> vec = {-4, 5, -2, -3};
    Display(vec);
    int prod = MaxProduct_SubArray(vec);
    cout << "Max product of sub array : " << prod << endl;

    vector<int> vec1 = {-4, 5, 0, -2, -3, 10};
    Display(vec1);
    prod = MaxProduct_SubArray(vec1);
    cout << "Max product of sub array : " << prod << endl;

    vector<int> vec2 = {-1, 1, 0 };
    Display(vec2);
    prod = MaxProduct_SubArray(vec2);
    cout << "Max product of sub array : " << prod << endl;

    return 0;
}

Output

Array : -4 5 -2 -3 
Max product of sub array : 40
Array : -4 5 0 -2 -3 10 
Max product of sub array : 60
Array : -1 1 0 
Max product of sub array : 1



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.