Data Structures and Algorithms in Java – Arrays – Maximum Product Subarray

Problem:

Given an array of integers, find a continuous sub array in this array such that the product of its numbers is maximum among all sub arrays. Just return the value of the product.

Input:

Consider the input:

input = [1,-2,-3,0,7,-8,-2]

there are many possible continuous sub arrays like [1], [1,-2], [1,-2,-3] … [-3,0],[-3,0,7,-8] etc..

You need to find such sub array which has the maximum product.

Output:

For the above input , the maximum product sub array is [ 7,-8,-2] which has the product value of 7* -8 *-2 = 112

Try out the solution here:

https://leetcode.com/problems/maximum-product-subarray/

Solution:

The brute force solution for this problem is to iterate through each element of the array and multiply it with rest other subsequent elements and find out the maximum among them.

Here is the code:

class Solution {
    public int maxProduct(int[] nums) {
     
        
        
        int maxProduct = nums[0];
        
        
        for(int i=0;i<nums.length;i++){
            
            int product = nums[i];
             if(product > maxProduct){
                 
                 maxProduct = product;
             }
            
            
            for(int j=i+1 ;j<nums.length;j++){
                
                product = product * nums[j];
                
                if(product > maxProduct){
                    
                    maxProduct = product;
                }
            }
        }
        
        return maxProduct;
    }
}

The time complexity of the above algorithm is O(n² ).

A better solutions exists of time complexity O(n) and extra space complexity of O(1).

Hint:

1. While iterating through the array , keep track of the minimum of (current element , current element multiplied by previous minimum element , current element multiplied by previous maximum element)
2. Similarly keep track of the maximum of (current element , current element multiplied by previous mimimum element , current element multiplied by previous maximum element)
3. Find the maximum of the current maximum element and the overall maximum element

Algorithm:

STEP1: Initialize three variables to the first element of the array, max to represent the ouput , currentMax to represent the current maximum product as you traverse the array and currentMin to represent the current minimum product.

STEP2: For each element in the array , calculate the minimum of the current element , the product of the current element and the previous minimum element (currentMin) and the product of the current element and the previous maximum element(currentMax)

STEP2 a: Similarly calculate the maximum of the current element , the product of the current element and the previous minimum element(currentMin) and the product of the current element and the previous maximum element(currentMax).

STEP2 b: Find the maximum of the currentMax thus calculated and the existing max value

STEP 2c: Return max

Let’s implement this through an example:

Consider the input:

input = [1,-2,-3,0,7,-8,-2]

Initialize three variables ,

a variable to represent the maximum product (which is the output we want)

a variable to represent the current maximum product as we traverse the input array

a variable to represent the current minimum products as we traverse the input array.

Initialize all these variables to the first element .

In the above example , it is 1.

So

max = 1

currentMax = 1

currentMin = 1

Now for the rest of the elements , find currentMax , currentMin and update max accordingly .

currentMax is the maximum of (the previous currentMax multiplied by the current element , previous currentMin multiplied by the current element and the current element itself)

currentMin is the minimum of (the previous currentMin multiplied by the current element, previous currentMax multiplied by the current element and the current element itself)

max is the maximum of the( currentMax and the max calculated in the previous iteration)

In the first iteration:

max = 1 , currentMax = 1 , currentMin = 1 , current element = -2 (input[1])

Maximum of ( current element , currentMax * current element , currentMin * current element) which is

Maximum of ( -2, -2*1 , -2*1 ) = Maximum of (-2,-2,-2) = -2 (currentMax)

Minimum of ((-2,-2,-2) = -2 (currentMin)

max = Maximum of (currentMax , max ) = Maximum of ( -2,1) = 1

In the second iteration

max = 1 , currentMax = -2 , currentMin = -2 , current element = (input[2]) = -3

currentMax = Maximum of (current element , currentMax * current element , currentMin * currentElement) = Maximum of ( -3, -2 * -3 , -2*-3) = Max of (-3,6,6) = 6

currentMin = Min of (-3,6,6) = -3

max = Max of (currentMax , max ) = Max of (6,1) = 6

In the third iteration

max = 6, currentMax = 6, currentMin = -3 , current element = input[3] = 0

Now ,

currentMax = Max of (0, 0 * 6 , 0*-3) = Max of (0,0,0) = 0

currentMin = Min of (0,0,0) = 0

max = Max of (0,6) = 6

In the fourth iteration:

max = 6, currentMax = 0 , currentMin = 0, input[4] = 7

so ,

currentMax = Max of (7, 7*0,7*0) = Max of (7,0,0) = 7

currentMin = Min of (7,0,0) = 0

max = Max of (7,6) = 7

In the fifth iteration

max = 7, currentMax = 7,currentMin = 0, input[5] = -8

so ,

currentMax = Max of (-8,-8*7, -8*0) = Max of (-8,-56,0) = 0

currentMin = Min of (-8,-56,0) = -56

max = Max of (0,7) = 7

In the sixth iteration

max = 7, currentMax = 0, currentMin = -56 , input[6]=-2

so,

currentMax = Max of (-2, -2*0,-2*-56) = Max of (-2,0,112) = 112

currentMin = Min of (-2,0,112) = -2

max = Max of (112,7) = 112

Maximum value is 112!

Code:

Here is the code:

class Solution {
    public int maxProduct(int[] nums) {
     
        
       int max = nums[0];
        
        int currentMin = nums[0];
        
        int currentMax = nums[0];
        
        
        for(int i=1;i<nums.length;i++){
            
            
             int temp = Math.min(Math.min(nums[i],nums[i]*currentMin),nums[i]*currentMax);
            
              currentMax = Math.max(Math.max(nums[i],nums[i]*currentMin),nums[i]*currentMax);
            
            currentMin = temp;
            
            max = Math.max(currentMax, max);
            
                      
            
        }
        
        return max;
    }
}

The time complexity of the above algorithm is O(n) and extra space complexity is O(1) (the output variable , the rest variables can be ignored)

That’s it!

Reference:

https://www.geeksforgeeks.org/maximum-product-subarray/