DP - Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: subarray [2, 3] has largest product 6.

Input: nums = [-2, 0, -1]
Output: 0
Explanation: any sub array you consider max product is 0.

Solution 1 - using brute force approach
Solution 2 - efficient approach using dynamic programming

In this approach, we will generate all possible subarrays starting from each index in in the array and compute the product of subarrays and take the maximum product.

Say for example if the input array nums is [2, 3, -2, 4], we will then generate possible subarrays starting at 2, 3, -2 and 4 as shown below

Subarrays starting from 2:
- [2] => product = 2
- [2, 3] => product = 6
- [2, 3, -2] => product = -12
- [2, 3, -2, 4] => product = -48
Subarrays starting from 3:
- [3] => product = 3
- [3, -2] => product = -6
- [3, -2, 4] => product = -24
Subarrays starting from -2:
- [-2] => product = -2
- [-2, 4] => product = -8
Subarrays starting from 4:
- [4] => product = 4

As you can see above the maximum product subarrray value is 6 and that will be our answer.

Implementation details:

We will create a function bruteForceApproach that takes input nums array.
Define a variable max and initialize that with Integer.MIN_VALUE, since we are trying to find maximum product value, we are initializing this with lower bound of integer, so that it makes easy for comparisons.
Then generate all possible subarrays starting from each index in nums array using two for loops: for(int i=0; i<nums.length; i++) { for(int j=i; j<nums.lenth; j++) { ... } }
Then for each number from the subarray compute the product and keep track of maximum product found so far and finally return that max value;

public class MaximumProductSubArray { /* brute force approach*/ static int bruteForceApproach(int[] nums) { int max = Integer.MIN_VALUE; for(int i=0; i< nums.length; i++) { int maxProductAtI = 1; // initializing this with 1, because it's a neutral value for multiplication for(int j=i; j<nums.length; j++) { maxProductAtI = maxProductAtI * nums[j]; max = Math.max(max, maxProductAtI); } } return max; } }

Complexity Analysis:

Time complexity: Above code runs in O(n²) time where n is the length of input nums array, this is because we are generating all possible subarrays starting from each index in the array.
Space complexity: O(1) since we keep track of max value only.

In the above implementation, we have created substrings using the indexes for easiness of understanding, but when we call the function recursively we could also pass starting index as parameter and avoid creating substrings.

Intution behind this solution is, when we look at numbers from the input array there may be different combinations that could result in maximum product sub array. Consider below scenarios:

Scenario 1: when we have all positive integers, for example [1, 2, 5, 6] then the maximum product is product of all elements from the array.
Scenario 2: when we have all negative integers, there could be two scenarios when all numbers are negative, that is when the array length is odd and when it is even.
Consider input array as [-1, -2, -3, -5] then maximum product subarray is full length array, maximum product is product of all numbers, because even length array will result in positive product value.
Consider input array as [-1, -2, -3] then maximum product sub array is the subarray, excluding higher value number from left end of array or right end of array, that makes it even length subarray with maximum product. In this example it will be [-2, -3]
Scenario 3: when we have mix of positive and negative numbers, for example [1, 2, -5, 7], in this example we can clearly see that the maximum product is the subarray [7].
Scenario 4: when we have value 0 somewhere in the array, for example [1, 2, 0, 5, 6] , in this case 0 divides the array into two and the maximum product could be on left side subarray or it could be on right side subarray. If we have more than one 0 in the array, then again maximum product could be in any of the subarrays split by those 0's.

As you see from above scenarios, it will become tricky when the input array has both positive and negative numbers mixed and when there are 0's.

So, in this approach, what we are going to do is, we are going to maintain maximum product and minimum product values at each index and the reason we do that, consider this example input array [-1, 5, -6]:

When we are at 1^st element -1, maximum product will be -1.
When we are at 2^nd element 5, product of 1^st and 2^nd elements will be -5, at this point we may ignore the 1^st element and just consider just 2^nd element alone to be part of maximum product subarray, but this is not correct because at this point we do not know if the next coming number will make the product value higher or not.

So, by keeping both maximum and minimum prodoct values at each index, we check where product between min * current or max * current or current is resulting in higher value.

max = MAX (current, min*current, max*current); min = MIN (current, min*current, max*current);

This logic handles 0's as well, for example consider input array as [2, 0, 4, -2]

When we are at 1^st element 2. max =2; min =2;
When we are at 2^nd element 0. max = MAX(0, 2 * 0, 2 * 0); = 0 min = MIN(0, 2 * 0, 2 * 0); = 0
When we are at 3^rd element 4. max = MAX(4, 0 * 4, 0 * 4); = 4 min = MIN(4, 0 * 4, 0 * 4); = 0
When we are at 4^th element -2. max = MAX(-2, 4 * -2, 0 * -2); = 4 min = MAX(-2, 4 * -2, 0 * -2); = -8
As you can see maximum product is 4. As we loop through, will store the maximum product found so far in a variable and return that.

public class MaximumProductSubArray { /* DP efficient approach*/ static int dpApproach(int[] nums) { int result = nums[0]; int max_so_far = result; int min_so_far = result; for(int i=1;i<nums.length; i++) { int temp = max_so_far * nums[i]; max_so_far = Math.max(nums[i], Math.max(temp, min_so_far * nums[i])); min_so_far = Math.min(nums[i], Math.min(temp, min_so_far * nums[i])); result = Math.max(result, max_so_far); } return result; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input nums array.
Space complexity: O(1) as we are only keep tracking of 3 variables max, min and result.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis: