Maximum Subarray Product ā Problem Statement & Solution Guide
Problem Description
You are given an array of integers values representing commodity multipliers. Write a function to find the maximum product of a subarray within the given array, where the subarray must contain at least one element.
Examples
Input
[2,3,-2,4]
Output
6
Explanation: Step-by-step: We initialize maxProduct and minProduct to the first element of the array, which is 2. Then, we iterate through the array. For the second element 3, we update maxProduct to be the maximum of 2 * 3 and 3, which is 6. For the third element -2, we update maxProduct to be the maximum of 6 and -2 * 6, which is 6. For the fourth element 4, we update maxProduct to be the maximum of 6 and 4 * 6, which is 24. However, we also need to consider the case where the maxProduct becomes negative. For the second element 3, we update minProduct to be the minimum of 2 * 3 and 3, which is 6. For the third element -2, we update minProduct to be the minimum of 6 and -2 * 6, which is -12. For the fourth element 4, we update minProduct to be the minimum of -12 and 4 * -12, which is -48. Finally, we return maxProduct, which is 24.
Input
[0,0,0]
Output
0
Explanation: Step-by-step: We initialize maxProduct to 0. Then, we iterate through the array. For the first element 0, we update maxProduct to be the maximum of 0 * 0 and 0, which is 0. For the second element 0, we update maxProduct to be the maximum of 0 and 0 * 0, which is 0. For the third element 0, we update maxProduct to be the maximum of 0 and 0 * 0, which is 0. Finally, we return maxProduct, which is 0.
Constraints
- The input array will have at least one element.
- The input array will contain only integers between -100 and 100.
Optimal Approach & Strategy
The optimal approach uses dynamic programming to keep track of the maximum and minimum product of subarrays ending at each position, allowing it to handle negative numbers and find the maximum product in linear time.
Brute Force Approach
A naive approach would be to generate all possible subarrays, calculate their product, and keep track of the maximum product found. This would have a time complexity of O(nĀ²) due to the nested loops. However, this approach is inefficient for large inputs.
Verified Code Solutions
function maxSubarrayProduct(values) {
if (values.length === 0) return 0;
let maxProduct = values[0];
let minProduct = values[0];
let result = values[0];
for (let i = 1; i < values.length; i++) {
const current = values[i];
maxProduct = Math.max(Math.max(maxProduct * current, current), maxProduct * minProduct);
minProduct = Math.min(Math.min(minProduct * current, current), maxProduct * current);
result = Math.max(result, maxProduct);
}
return result;
}class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
int maxProduct = minProduct = result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);
result = Math.max(result, maxProduct);
}
return result;
}
}def maxProduct(nums):
if not nums:
return 0
max_product = min_product = result = nums[0]
for num in nums[1:]:
if num < 0:
max_product, min_product = min_product, max_product
max_product = max(num, max_product * num)
min_product = min(num, min_product * num)
result = max(result, max_product)
return resultfunction maxSubarrayProduct(values) {
if (values.length === 0) return 0;
let maxProduct = values[0];
let minProduct = values[0];
let result = values[0];
for (let i = 1; i < values.length; i++) {
const current = values[i];
maxProduct = Math.max(Math.max(maxProduct * current, current), maxProduct * minProduct);
minProduct = Math.min(Math.min(minProduct * current, current), maxProduct * current);
result = Math.max(result, maxProduct);
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.