Maximum Product Subarray Editorial

Practice Problem Link: Maximum Product Subarray | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A of integers, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

Naive Approach

Here, we can iterate over all the possible subarrays in the array, and calculate the maximum product out of all the subarrays. We can do this by fixing 2 indexes i and j, and iterating over the subarray starting at i and ending at j.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

int maxProduct(vector<int> A) {
   int maxProductValue = INT_MIN;
   for(int i = 0; i < A.size(); i++) {
       for(int j = i; j < A.size(); j++) {
           int product = 1;
           for(int k = i; k <= j; k++) {
               product *= A[k];
           }
           maxProductValue = max(maxProductValue, product);
       }
   }
   return maxProductValue;
}

Java

class Solution {
   int maxProduct (int[] A) {
       int maxProductValue = Integer.MIN_VALUE;
       for(int i = 0; i < A.length; i++) {
           for(int j = i; j < A.length; j++) {
               int product = 1;
               for(int k = i; k <= j; k++) {
                   product *= A[k];
               }
               maxProductValue = Math.max(maxProductValue, product);
           }
       }
       return maxProductValue;
   }
}

Optimal Approach

If all the numbers in the array were positive, the answer will definitely be the product of the whole array.

If we now consider the case, when there are no negative numbers in the array, we can approach it as soon as we encounter a 0, we reset our product to 1 and keep taking the maximum product in each iteration.

With the introduction of negative numbers, we now have to keep track of the maximum positive product and the maximum negative product. When we encounter a negative number, the maximum negative product is taken into consideration.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int maxProduct(vector<int> A) {
   if(A.size() == 1) {
       return A[0];
   }
   int currMax = A[0], currMin = A[0], maxProductValue = A[0];
   for(int i = 1; i < A.size(); i++) {
       if(A[i] >= 0) {
           currMax = max(A[i], A[i] * currMax);
           currMin = min(A[i], A[i] * currMin);
           maxProductValue = max(maxProductValue, currMax);
       } else {
           swap(currMin, currMax);
           currMax = max(A[i], A[i] * currMax);
           currMin = min(A[i], A[i] * currMin);
           maxProductValue = max(maxProductValue, currMax);
       }
   }
   return maxProductValue;
}

Java

class Solution {
   int maxProduct (int[] A) {
       if(A.length == 1) {
           return A[0];
       }
       int currMax = A[0], currMin = A[0], maxProductValue = A[0];
       for(int i = 1; i < A.length; i++) {
           if(A[i] >= 0) {
               currMax = Math.max(A[i], A[i] * currMax);
               currMin = Math.min(A[i], A[i] * currMin);
               maxProductValue = Math.max(maxProductValue, currMax);
           } else {
               int temp = currMax;
               currMax = currMin;
               currMin = temp;
               currMax = Math.max(A[i], A[i] * currMax);
               currMin = Math.min(A[i], A[i] * currMin);
               maxProductValue = Math.max(maxProductValue, currMax);
           }
       }
       return maxProductValue;
   }
}