Last Updated: 1 Feb, 2021
Maximum Product Subarray
Moderate
Asked in companies
You are given an array “arr'' of integers. Your task is to find the contiguous subarray within the array which has the largest product of its elements. You have to report this maximum product.
An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.
For e.g.- The non-empty subarrays of an array [1,2,3] will be- [1],[2],[3],[1,2],[2,3],[1,2,3].
For Example:
If arr = {-3,4,5}.
All the possible non-empty contiguous subarrays of “arr” are {-3}, {4}, {5}, {-3,4}, {4,5} and {-3,4,5}.
The product of these subarrays are -3, 4, 5, -12, 20 and -60 respectively.
The maximum product is 20. Hence, the answer is 20.
Follow Up:
Can you solve this in linear time and constant space complexity?
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains a single integer N, denoting the number of elements of the array “arr”.
The second line of each test case contains N space separated integers denoting the elements of the array “arr”.
Output format:
For each test case, print the maximum product of the contiguous non-empty subarray of the array “arr”.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
-100 <= arr[i] <= 100
where N is the size of the array “arr”.
Time limit: 1 second
Approaches
Steps:
- Create an ans variable and initialize it to INT_MIN.
- Run a loop i = 0 to N and do:
- Run a loop j = i to N and do:
- Create a variable, say currentProduct and initialize it to 1.
- Run a loop k = i to j and do:
- currentProduct = currentProduct * arr[k]
- Store the maximum of ans and the currentProduct in the ans variable.
- Run a loop j = i to N and do:
- Finally, return the ans variable.
Steps:
- Create an ans variable and initialize it to INT_MIN.
- Run a loop i = 0 to N and do:
- Create a variable, say currentProduct and initialize it to arr[i].
- Store the maximum of ans and the currentProduct in the ans variable.
- Run a loop from j = i + 1 to N and do:
- currentProduct = currentProduct * arr[j].
- Store the maximum of “ans” and the “currentProduct” in the “ans” variable.
- Finally, return the “ans” variable.
In the previous approach, we were trying to find the product of all the possible subarrays of the array. But, we can optimize this approach with a simple trick. Note that the product of an even number of negative integers is a positive integer.
Now, let’s say the number of negative integers in a subarray of the array is P. If P is even, then we should take all the negative integers as the product of these elements will be positive. If P is odd, then we have to take P - 1 negative integer. Since this has to be a contiguous subarray, so we can either exclude one negative integer from the beginning or from the end.
So, we can take two integers to calculate the product from the beginning and the product from the end of the array. We will traverse the array “arr”, multiply arr[i] with the product from the beginning and arr[N - i - 1] with the product from the end. Then calculate the maximum of these two products in every iteration. Also, if at any point, if we encounter a 0, i.e. if either of the products become 0, then make that product 1 again.
Steps:
- Create an ans variable and initialize it to INT_MIN. Create two more integers i.e. productFromFront, productFromBack. Initialize them to 1.
- Now for each i from 0 to N - 1:
- productFromFront = productFromFront * arr[i]
- productFromBack = productFromBack * arr[N - i - 1]
- Store the maximum of ans, productFromFront and productFromBack in the ans variable.
- If productFromFront becomes 0, make productFromFront = 1.
- If productFromBack becomes 0, make productFromBack = 1.
- Finally, return the ans variable.
Similar problems