Finding Maximum Product Sub-array in a Given Array in C++

Understanding Maximum Product Sub-array

This task involves finding the contiguous sub-array within a given array that has the maximum product.

We will explore three different methods to achieve this in C++.

Method 1: Using a Simple Iterative Approach

This method iterates through the array and keeps track of the maximum product.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int maxProductSubArray(vector& arr) {
    int max_product = INT_MIN;
    for (int i = 0; i < arr.size(); i++) {
        int product = 1;
        for (int j = i; j < arr.size(); j++) {
            product *= arr[j];
            max_product = max(max_product, product);
        }
    }
    return max_product;
}

int main() {
    vector arr = {2, 3, -2, 4};
    cout << "Maximum Product Sub-array: " << maxProductSubArray(arr) << endl;
    return 0;
}
            

Method 2: Using Dynamic Programming (Kadane's Algorithm Variant)

This method optimally finds the maximum product sub-array using dynamic programming.

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

using namespace std;

int maxProductSubArray(vector& arr) {
    int max_product = arr[0], min_product = arr[0], result = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < 0) swap(max_product, min_product);
        max_product = max(arr[i], max_product * arr[i]);
        min_product = min(arr[i], min_product * arr[i]);
        result = max(result, max_product);
    }
    return result;
}

int main() {
    vector arr = {2, 3, -2, 4};
    cout << "Maximum Product Sub-array: " << maxProductSubArray(arr) << endl;
    return 0;
}
            

Method 3: Using Recursion

This method uses recursion to find the maximum product sub-array.

#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;

int maxProductRec(vector& arr, int start, int end, int& result) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    int leftMax = maxProductRec(arr, start, mid, result);
    int rightMax = maxProductRec(arr, mid + 1, end, result);
    result = max({result, leftMax, rightMax});
    return result;
}

int maxProductSubArray(vector& arr) {
    int result = INT_MIN;
    return maxProductRec(arr, 0, arr.size() - 1, result);
}

int main() {
    vector arr = {2, 3, -2, 4};
    cout << "Maximum Product Sub-array: " << maxProductSubArray(arr) << endl;
    return 0;
}