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