Maximum product subarray

Given an array with n elements. Find the contiguous subarray (within the given array) with the highest product

Example Test Cases

Sample Test Case 1

Array: 2, 3, -6, 0, 4, 10
Expected Output: 40
Explanation: Out of all the possible subarrays 40 is the maximum possible product which is obtained by multiplying subarry [4, 10] .

Sample Test Case 2

Array: 2, 3, -6, -4, 10
Expected Output: 1440
Explanation: In this case we can multiply all the numbers together and get 1440 as the answer.

Solution

We can divide the types of arrays into the following cases:

• Case 1 : If there are no zeroes within the array and there are even number of negative numbers. In this case, we can simply multiply all the numbers together and get an answer. Since the no of negative numbers is even, all the negatives will cancel each other out and in the end we will get a positive number which will be our answer.

• Case 2 : If there are no zeroes within the array and there are an odd number of negative numbers and the number of negative numbers is at least 3. In this case, if we multiply all the numbers then the resulting product would be negative. Therefore, to make the product positive we can either exclude the leftmost negative number (and all the elements left to it) or we can exclude the right most negative number (and all the elements towards it’s right). We will exclude whichever gives us highest answer after excluding it.

• Case 3: If there are no zeroes within the array and there is only one negative number in the array. In this case, the answer would be just the product of all the numbers to the left of negative number or the product of all the numbers to the right of the negative number.

• Case 4: If there are zeroes within the array. In this case, we can find the maximum product of the subarrays b/w zeroes (excluding zero). Since, we have excluded zeroes from the subarray, it will fall into either one of Case 1, 2 or 3 described above and the max over all of the possible subarrays is the answer.
  For array [ 2, 3, -1, 5, 0, 3, 4, 1, 0 , 6, -10, -3 ], we will try to find the maximum product of subarray [ 2, 3, -1, 5 ] and [3, 4, 1 ] and [ 6, -10, -3 ]. For the first subarray, the answer is 6 (from case 3 above), the 2nd subarray the answer is 12 (from Case 1 above) and for 3rd subarray the answer is 180 (from Case 1 above). The maximum of these three is 180 which is our answer.

See the code below for implementation

Implementation

#include <bits/stdc++.h>
using namespace std;

// This is used to compute the maximum product of a subarray without zero.
int maxWZero(vector& nums) {
    if (nums.size() == 1) {
        return nums[0];
    }
    // complete product of nums
    int fullProd = 1;
    // used to store the position of the first and last negative number
    pair<int, int> neg = make_pair(-1, -1);

    int noOfNegative = 0;

    for(int i = 0; i < nums.size(); i++) {
        fullProd = fullProd * nums[i];
        if (nums[i] < 0 && neg.first < 0) {
            neg.first = i;
        }
        else if (nums[i] < 0 && neg.second < i) {
            neg.second = i;
        }
        if (nums[i] < 0) {
            noOfNegative++;
        }
    }
    // Since the no of negative is only 1, both the first and second negative numbers are the same.
    if (noOfNegative == 1) {
        neg.second = neg.first;
    }
    // Case 1
    if (noOfNegative%2 == 0) {
        return fullProd;
    }
    // Case 2
    else {
        int p1 = nums[neg.first], p2 = nums[neg.second];
        for(int i = 0; i < neg.first; i++) {
            p1 = p1 * nums[i];
        }
        for(int i = nums.size() - 1; i > neg.second; i--) {
            p2 = p2 * nums[i];
        }
        return max(fullProd/p1, fullProd/p2);
    }
}

int main() {
   vector nums = {2, 3, -1, 5, 0, 3, 4, 1, 0, 6, -10, -3}; 
   // used to store the subarrays without zero. 
   vector<vector> compressed;
   int n = nums.size(); 
   int i = 0; 
   while(i < n) {
       if (nums[i] == 0) {
           i++;
           continue;
       }
       int j = i;
       vector cp;
       while (j < n) {
           if (nums[j] != 0) {
               cp.push_back(nums[j]);
               j++;
           }
           else {
               j++;
               break;
           }
       }
       if (cp.size() > 0) {
           compressed.push_back(cp);
       }
       i = j;
   }
   int maxVal = INT_MIN;
   for(int i = 0; i < nums.size(); i++) {
       maxVal = max(maxVal, nums[i]);
   } 
   for(int i = 0; i < compressed.size(); i++) {
       maxVal = max(maxVal, maxWZero(compressed[i]));
   }
   cout << "Maximum product of the array is " << maxVal << "\n";
   return (0);
}