Forward and Backward Passes
In the Maximum Product Subarray problem, the Forward Pass involves iterating through the given array once, starting from the first element. During this pass, you calculate the local maximum and minimum product for each subarray ending at position i
. The reason for keeping track of both maximum and minimum is because a negative number can become positive when multiplied by another negative number.
The Backward Pass is similar to the Forward Pass but starts from the last element and moves towards the first. This pass also calculates local maximum and minimum product subarrays. The Backward Pass ensures that we explore all subarrays, accounting for changes in sign which might yield a larger product.
Example Code
Java:
Forward Pass
1
2
3
4
5
6
7
8
9
10
| public int forwardPass(int[] nums) {
int maxProduct = nums[0], minProduct = nums[0], result = nums[0];
for(int i = 1; i < nums.length; i++) {
int tempMax = maxProduct;
maxProduct = Math.max(nums[i], Math.max(maxProduct * nums[i], minProduct * nums[i]));
minProduct = Math.min(nums[i], Math.min(tempMax * nums[i], minProduct * nums[i]));
result = Math.max(result, maxProduct);
}
return result;
}
|
Backward Pass
1
2
3
4
5
6
7
8
9
10
| public int backwardPass(int[] nums) {
int maxProduct = nums[nums.length - 1], minProduct = nums[nums.length - 1], result = nums[nums.length - 1];
for(int i = nums.length - 2; i >= 0; i--) {
int tempMax = maxProduct;
maxProduct = Math.max(nums[i], Math.max(maxProduct * nums[i], minProduct * nums[i]));
minProduct = Math.min(nums[i], Math.min(tempMax * nums[i], minProduct * nums[i]));
result = Math.max(result, maxProduct);
}
return result;
}
|
C++:
Forward Pass
1
2
3
4
5
6
7
8
9
10
| int forwardPass(vector<int>& nums) {
int maxProduct = nums[0], minProduct = nums[0], result = nums[0];
for(int i = 1; i < nums.size(); ++i) {
int tempMax = maxProduct;
maxProduct = max(nums[i], max(maxProduct * nums[i], minProduct * nums[i]));
minProduct = min(nums[i], min(tempMax * nums[i], minProduct * nums[i]));
result = max(result, maxProduct);
}
return result;
}
|
Backward Pass
1
2
3
4
5
6
7
8
9
10
| int backwardPass(vector<int>& nums) {
int maxProduct = nums.back(), minProduct = nums.back(), result = nums.back();
for(int i = nums.size() - 2; i >= 0; --i) {
int tempMax = maxProduct;
maxProduct = max(nums[i], max(maxProduct * nums[i], minProduct * nums[i]));
minProduct = min(nums[i], min(tempMax * nums[i], minProduct * nums[i]));
result = max(result, maxProduct);
}
return result;
}
|
Python:
Forward Pass
1
2
3
4
5
6
7
8
| def forward_pass(nums):
max_product = min_product = result = nums[0]
for i in range(1, len(nums)):
temp_max = max_product
max_product = max(nums[i], max_product * nums[i], min_product * nums[i])
min_product = min(nums[i], temp_max * nums[i], min_product * nums[i])
result = max(result, max_product)
return result
|
Backward Pass
1
2
3
4
5
6
7
8
| def backward_pass(nums):
max_product = min_product = result = nums[-1]
for i in range(len(nums) - 2, -1, -1):
temp_max = max_product
max_product = max(nums[i], max_product * nums[i], min_product * nums[i])
min_product = min(nums[i], temp_max * nums[i], min_product * nums[i])
result = max(result, max_product)
return result
|
To find the maximum product subarray, you can run both Forward and Backward Pass and take the maximum of the two results.