The Maximum Product Subarray problem asks you to find the highest possible product from any sequence of consecutive numbers (or “subarray”) within a given list of integers. You’re not just looking for the largest single number, but rather the maximum product you can achieve by multiplying a series of numbers that appear in sequence in the array.
Brute Force Approach
A brute-force approach is a simple way to solve this by calculating the product of every possible subarray and returning the maximum value found. This approach is not efficient but helps us understand the problem.
public int maxProductBruteForce(int[] nums) {
int maxProduct = nums[0];
for (int i = 0; i < nums.length; i++) {
int product = 1;
for (int j = i; j < nums.length; j++) {
product *= nums[j];
maxProduct = Math.max(maxProduct, product);
}
}
return maxProduct;
}
The code initializes maxProduct with the first element. It then uses two nested loops, where the outer loop picks a starting point, and the inner loop computes the product of subarrays starting from that point. At each step, the maximum product is updated. This solution has high time complexity (O(n²)), as it checks every possible subarray.
Optimal Solution: Dynamic Programming Approach
To solve this problem optimally, we can use dynamic programming. We maintain two values for each position in the array: the maximum and minimum product up to that point. This way, we handle both positive and negative products efficiently. We track the maximum product seen so far and update it as we iterate through the array.
This dynamic programming pattern is ideal when:
• You need to keep track of cumulative subarray values.
• The problem has elements that interact (in this case, negative numbers affecting the sign of products).
• There’s a need for optimal subproblem solutions without recalculating previously computed values.
The dynamic programming approach is more efficient because it reduces unnecessary calculations. It has a time complexity of O(n) and space complexity of O(1), as it only keeps track of two values per iteration instead of recalculating products for every subarray.
Steps of the Algorithm
1. Initialize maxProduct, minProduct, and result with the first element.
2. Iterate through the array from the second element.
3. For each element, update maxProduct and minProduct by considering the current number, the product with the previous maxProduct, and minProduct.
4. Update result to keep track of the maximum product found.
5. Return result at the end.
public int maxProduct(int[] nums) {
int maxProduct = nums[0]; // Stores the max product up to the current position
int minProduct = nums[0]; // Stores the min product up to the current position
int result = nums[0]; // Tracks the highest product encountered so far
for (int i = 1; i < nums.length; i++) {
int current = nums[i];
// Calculate temporary maxProduct considering the current value
int tempMax = Math.max(current, Math.max(maxProduct * current, minProduct * current));
// Update minProduct using current and previous max/min values
minProduct = Math.min(current, Math.min(maxProduct * current, minProduct * current));
// Update maxProduct to the temporary max
maxProduct = tempMax;
// Update result if the current maxProduct is the highest found
result = Math.max(result, maxProduct);
}
return result;
}Step-By-Step Breakdown
- Initialize maxProduct, minProduct, and result
int maxProduct = nums[0]; // Stores the max product up to the current position
int minProduct = nums[0]; // Stores the min product up to the current position
int result = nums[0]; // Tracks the highest product encountered so far- We start by initializing maxProduct, minProduct, and result with the first element in the array. This is because, at the beginning, the only “subarray” we have is the first element itself.
- The maxProduct will keep track of the largest product we can achieve up to the current index, while minProduct will track the smallest product. This is crucial because a small negative product can become the maximum if it’s multiplied by another negative number.
2. Loop through the array from second element
for (int i = 1; i < nums.length; i++) {
int current = nums[i];- We start the loop from the second element because we already used the first element to initialize our variables. At each step, current holds the value of the current number in the array.
- Loop is to check each element to update maxProduct, minProduct, and result.
3. Calculate maximum product at the current position
int tempMax = Math.max(current, Math.max(maxProduct * current, minProduct * current));
This line calculates the possible maximum product at the current position by considering three cases:
- current by itself, restarting the subarray.
- maxProduct * current, extending the current maximum product.
- minProduct * current, in case multiplying two negative numbers yields a larger positive product.
We temporarily store this value in tempMax because we’ll need to update minProduct first before assigning it back to maxProduct. This allows us to keep the values independent until both are updated.
4. Update minProduct at the current position
minProduct = Math.min(current, Math.min(maxProduct * current, minProduct * current));- This line updates minProduct similary to tempMax, considering three cases:
- current alone, restarting the subarray
- maxProduct * current, which could be the minimum if current is negative.
- minProduct * current, extending the smallest product so far.
- Keeping track of the minimum product helps manage the effect of negative values, which can turn into large positives when multiplied again.
5. Update maxProduct with tempmax
maxProduct = tempMax;- Now, we update maxProduct with the calculated tempMax value. This ensures that maxProduct reflects the largest possible product at the current position.
- We only assign tempMax to maxProduct after calculating minProduct to ensure that we have the correct values at each step without interference.
6. Update result with the maximum product found so far
result = Math.max(result, maxProduct);- We update result to track the largest product of any subarray encountered so far.
- By updating result at each step, we ensure that the final value of result is the maximum product subarray for the entire array.
Why This Code Works
This approach is efficient because it only goes through the array once (O(n) time complexity) and uses a constant amount of extra space (O(1) space complexity). This is much faster than recalculating products for every possible subarray, as in the brute-force approach. The dynamic tracking of maxProduct and minProduct allows us to handle positive and negative numbers effectively, making this approach well-suited for the problem.
