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.