We can use Dynamic Programming or an iterative approach tracking both the maximum and minimum products up to the current element. Because a negative number can turn a large negative product into a large positive one, we must keep track of the minimum (most negative) product as well as the maximum product at each step.
// Pseudocode: Check every possible subarray product.
// 1. Initialize max_prod = INT_MIN.
// 2. For i from 0 to n-1:
// 3. curr_prod = 1
// 4. For j from i to n-1:
// 5. curr_prod *= nums[j]
// 6. max_prod = max(max_prod, curr_prod)
// 7. Return max_prod.
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
int curr = 1;
for (int j = i; j < nums.size(); ++j) {
curr *= nums[j];
res = max(res, curr);
}
}
return res;
}
};// Pseudocode:
// 1. Initialize res = max element in nums, curMin = 1, curMax = 1.
// 2. Iterate through each n in nums.
// 3. If n == 0, reset curMin = 1, curMax = 1.
// 4. Calculate tmp = curMax * n.
// 5. curMax = max({n * curMax, n * curMin, n}).
// 6. curMin = min({tmp, n * curMin, n}).
// 7. res = max(res, curMax).
// 8. Return res.
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = *max_element(nums.begin(), nums.end());
int curMin = 1, curMax = 1;
for (int n : nums) {
if (n == 0) {
curMin = 1;
curMax = 1;
continue;
}
int tmp = curMax * n;
curMax = max({n * curMax, n * curMin, n});
curMin = min({tmp, n * curMin, n});
res = max(res, curMax);
}
return res;
}
};Time: O(n) as we loop through the array once. Space: O(1) as we only use a few variables.
- Array contains zeroes. Zeroes reset the product. Handled by resetting curMax and curMin to 1.
- Array has only negative numbers. We need to return the max negative number, which works since we take
max(n)initially.
Always track the minimum product when dealing with array products with negative numbers. A large negative number multiplied by another negative number becomes a large positive number.