Maximum Product Subarray
Hello everyone, I'm Dhanraj, a CSIT Btech student currently pursuing my degree at Rajarambapu Institute of Technology. I'm a passionate web developer and Java programmer, with a keen interest in data structures and algorithms.
Programming has always been my passion since my school days, and I have been constantly exploring the world of computer science. My fascination with web development began when I discovered the power of the internet, and since then, I have been honing my skills to create beautiful, functional websites.
I believe that perseverance and hard work are the keys to success in any field, and programming is no exception. I enjoy the challenge of solving complex problems and take pride in delivering high-quality code that meets the requirements of my clients.
Apart from programming, I also have a keen interest in playing chess and expanding my knowledge of the stock market. I strongly believe that a well-rounded personality is crucial for success in life, and I always strive to balance my academic pursuits with my extracurricular activities.
I'm excited to share my experiences and knowledge with you through my blog. Whether you're a beginner or an experienced programmer, I hope that my articles will inspire you to push your limits and reach new heights in your programming journey.
Given an array Arr[] that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.
Example 1:
Input:
N = 5
Arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is [6, -3, -10] which gives product as 180.
Example 2:
Input:
N = 6
Arr[] = {2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is [2, 3, 4, 5] which gives product as 120.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Note: Use 64-bit integer data type to avoid overflow.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 500
-102 ≤ Arri ≤ 102
Explanation:
This is an explanation of the approach to solve a problem related to finding the maximum product subarray in an array, which is often asked in technical coding rounds during the hiring process. The approach involves understanding four conditions to solve the problem effectively.
The first condition is when all elements in the array are positive. For example, if we take an array such as [2, 2, 3, 4, 5], we can multiply all the elements together to get the maximum multiplication.
The second condition is when there are an even number of negative elements in the array. For instance, if we take an array like [2, -2, -3, 4, 5], we can multiply all the elements together to get the maximum multiplication.
The third condition is when the array contains an odd number of negative elements. For instance, if we take an array like [2, -2, 3, -4, 5, 6, -7, 1], there are two possible scenarios to consider. First, we can take -2 as the middle point and get [2] and [3, -4, 5, 6, -7, 1]. Second, we can take -7 as the middle point and get [2, -2, 3, -4, 5, 6] and [-7, 1].
The fourth condition is when the array contains zeros. When we multiply any number with 0, the multiplication becomes zero. Hence, when a zero appears in the array during traversal, we initialize prefix_product and suffix_product to 1.
Solution:
class Solution {
// Function to find maximum product subarray
long maxProduct(int[] arr, int n) {
long pref = 1;
long suf = 1;
long ans = Integer.MIN_VALUE;
for(int i=0; i<n; i++)
{
if(pref == 0)
pref=1;
if(suf == 0)
suf=1;
pref = pref * arr[i];
suf = suf* arr[n-i-1];
ans = Math.max(ans, Math.max(pref, suf));
}
return ans;
}
}