Given an array arr. The task is to find and return the maximum product possible with the subset of elements present in the array.
Note:
- The maximum product can be a single element also.
- Since the product can be large, return it modulo 109 + 7.
Examples:
Input: arr[] = [-1, 0, -2, 4, 3] Output: 24 Explanation: Maximum product will be ( -1 * -2 * 4 * 3 ) = 24
Input: arr[] = [-1, 0] Output: 0
Explanation: Maximum product will be ( -1 * 0) = 0
Input: arr[] = [5] Output: 5
Explanation: Maximum product will be 5.
Expected Time Complexity: \(O(n)\)
Expected Auxiliary Space: \(O(1)\)
Constraints:
1 <= arr.size() <= 2 * 104
-10 <= arr[i] <= 10
Approach 01:
-
C++
-
Python
class Solution {
public:
#define ll long long int
const ll MOD = 1e9 + 7;
long long int findMaxProduct(vector<int>& arr) {
ll product = 1;
ll numElements = arr.size();
ll negativeCount = 0;
ll negativeProduct = 1;
ll positiveCount = 0;
ll maxNegative = INT_MIN;
// Calculate the product of negative numbers and count positive numbers
for (int i = 0; i < numElements; ++i) {
if (arr[i] < 0) {
negativeCount++;
negativeProduct *= arr[i];
negativeProduct %= MOD;
maxNegative = max(maxNegative, (ll)arr[i]);
}
}
// If there is an odd number of negative numbers, exclude the largest (least negative) one
if (negativeCount % 2 == 1) {
negativeProduct /= maxNegative;
}
negativeProduct %= MOD;
// Calculate the product of positive numbers
for (int i = 0; i < numElements; ++i) {
if (arr[i] > 0) {
positiveCount++;
product *= arr[i];
product %= MOD;
}
product %= MOD;
}
// If there are no positive numbers and less than two negative numbers, the maximum product is 0
if (negativeCount <= 1 && positiveCount <= 0) {
return 0;
}
ll maxProduct = (product % MOD * negativeProduct % MOD) % MOD;
return maxProduct % MOD;
}
};
class Solution:
MOD = 10**9 + 7
def findMaxProduct(self, arr):
product = 1
numElements = len(arr)
negativeCount = 0
negativeProduct = 1
positiveCount = 0
maxNegative = float('-inf')
# Calculate the product of negative numbers and count positive numbers
for num in arr:
if num < 0:
negativeCount += 1
negativeProduct *= num
negativeProduct %= self.MOD
maxNegative = max(maxNegative, num)
# If there is an odd number of negative numbers, exclude the largest (least negative) one
if negativeCount % 2 == 1:
# Use modular multiplicative inverse
inverse_max_negative = pow(maxNegative, self.MOD-2, self.MOD)
negativeProduct *= inverse_max_negative
negativeProduct %= self.MOD
# Calculate the product of positive numbers
for num in arr:
if num > 0:
positiveCount += 1
product *= num
product %= self.MOD
# If there are no positive numbers and less than two negative numbers, the maximum product is 0
if negativeCount <= 1 and positiveCount <= 0:
return 0
maxProduct = (product * negativeProduct) % self.MOD
return maxProduct % self.MOD
Time Complexity
- Initialization:
Initializations and declarations take constant time \(O(1)\).
- Loops:
The main loops iterate over each element of the array twice, which takes \(O(n)\) time.
- Overall Time Complexity:
The overall time complexity is \(O(n)\).
Space Complexity
- Auxiliary Space:
The algorithm uses additional space for a few variables, resulting in \(O(1)\) space usage.
- Overall Space Complexity:
The overall space complexity is \(O(1)\).