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



© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The best error message is the one that never shows up. - Thomas Fuchs"