Maximum Product Subarray | GeeksForGeeks | Problem of the Day | Python | C++

Given an array arr[] that contains positive and negative integers (may contain 0 as well). Find the maximum product that we can get in a subarray of arr.

Note: It is guaranteed that the output fits in a 32-bit integer.

Examples

Input: arr[] = [-2, 6, -3, -10, 0, 2]
Output: 180
Explanation: The subarray with maximum product is {6, -3, -10} with product = 6 * (-3) * (-10) = 180.
Input: arr[] = [-1, -3, -10, 0, 60]
Output: 60
Explanation: The subarray with maximum product is {60}.
Input: arr[] = [2, 3, 4]
Output: 24
Explanation: For an array with all positive elements, the result is product of all elements.

#geeksforgeeks
#problemoftheday
#education
#computerscience
#coding
#array
#sorting
#sorts
#sort
#datastructure
#algorithmicproblemsolving
#algorithms
#algorithm
#dynamicprogramming
#dp
#potd
#gfg
#binarytree
#binarysearchtree
#bst
#string
#dictionary
#python
#stack
#queue
#python
#c++
#interview

Table of Contents
0:00 Problem Statement
0:34 Solution
3:12 Pseudo Code
5:50 Code - Python
7:00 Code - C++

[mathematics]

Table of Contents
0:00 Problem Statement
0:34 Solution
3:12 Pseudo Code
5:50 Code - Python
7:00 Code - C++

[mathematics]

import sys

class Solution:

# Function to find maximum
# product subarray
def maxProduct(self, arr):
lprod = rprod = 1
ans = -sys.maxsize
all_zero = True
i = 0
j = len(arr) - 1

while i < len(arr) and j >= 0:
if arr[i] != 0 or arr[j] != 0:
all_zero = False

if arr[i] != 0:
lprod *= arr[i]
else:
lprod = 1

if arr[j] != 0:
rprod *= arr[j]
else:
rprod = 1

prod = max(lprod, rprod)
ans = max(ans, prod)

i += 1
j -= 1

if all_zero:
return 0
return ans

[mathematics]

class Solution {
public:
// Function to find maximum product subarray
int maxProduct(vector<int> &arr) {
int lprod = 1, rprod = 1, ans = INT_MIN;
bool all_zero = true;

for (int i = 0, j = arr.size() - 1; i < arr.size() and j >= 0; i++, j--) {
if (arr[i] != 0 or arr[j] != 0)
all_zero = false;

if (arr[i] != 0)
lprod *= arr[i];
else
lprod = 1;

if (arr[j] != 0)
rprod *= arr[j];
else
rprod = 1;

int prod = max(lprod, rprod);
ans = max(ans, prod);
}

if (all_zero)
return 0;
return ans;
}
};