# Maximum Product Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-product-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-subarray
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Wayfair](https://scaleengineer.com/companies/wayfair), [Hiver](https://scaleengineer.com/companies/hiver), [HashedIn](https://scaleengineer.com/companies/hashedin), [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
Given an integer array `nums`, find a subarray that has the largest product, and return _the product_.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = [2,3,-2,4]
**Output:** 6
**Explanation:** [2,3] has the largest product 6.

**Example 2:**

**Input:** nums = [-2,0,-1]
**Output:** 0
**Explanation:** The result cannot be 2, because [-2,-1] is not a subarray.

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `-10 <= nums[i] <= 10`
* The product of any subarray of `nums` is **guaranteed** to fit in a **32-bit** integer.

# Approaches
## Brute Force by Checking All Subarrays
This approach iterates through all possible contiguous subarrays, calculates the product of each, and keeps track of the maximum product found. It's the most straightforward but least efficient method.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Guaranteed to find the correct solution as it checks every possibility.
**Cons:** Highly inefficient with a time complexity of O(n^2), making it too slow for large inputs.; Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The brute-force method systematically considers every possible subarray. We can define a subarray by its starting and ending indices.

We use two nested loops. The outer loop, with index `i`, selects the start of the subarray. The inner loop, with index `j`, selects the end of the subarray.

For each subarray `nums[i...j]`, we calculate its product. A running product can be maintained within the inner loop to avoid a third loop for calculation. The maximum product found across all subarrays is updated and stored. The initial maximum product can be set to the first element of the array to handle cases where all numbers are negative.

```java
class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int maxProduct = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int currentProduct = 1;
            for (int j = i; j < nums.length; j++) {
                currentProduct *= nums[j];
                if (currentProduct > maxProduct) {
                    maxProduct = currentProduct;
                }
            }
        }
        return maxProduct;
    }
}
```
### Algorithm
- Initialize `max_product` with the first element of `nums`.
- Iterate through the array with index `i` from 0 to `n-1` (this will be the start of the subarray).
- Inside the first loop, initialize a `current_product` to 1.
- Start a nested loop with index `j` from `i` to `n-1` (this will be the end of the subarray).
- In the inner loop, multiply `current_product` by `nums[j]`.
- Compare `current_product` with `max_product` and update `max_product` if `current_product` is larger.
- After both loops complete, return `max_product`.

## Optimal Two Pass Approach
This clever approach finds the maximum product in a single pass by keeping track of the product from the left and the product from the right simultaneously. It correctly handles negative numbers and zeros.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Constant space complexity O(1).; Relatively simple to implement once the logic is understood.
**Cons:** The reasoning for its correctness, especially with an odd number of negative values, can be less intuitive than the dynamic programming approach.
### Explanation
The core idea is that the maximum product subarray will not contain a zero (unless the max product is zero itself). Zeros act as separators, breaking the problem into smaller subproblems.

For a subarray without zeros, the maximum product is either the product of all its elements (if there's an even number of negatives) or the product of a subsegment that excludes one of the endmost negative numbers (if there's an odd number of negatives).

By calculating prefix products (from left to right) and suffix products (from right to left), we are guaranteed to find these maximums. The left-to-right pass will find the maximum product for subarrays with an odd number of negatives that ends at the right boundary. The right-to-left pass handles the case where it ends at the left boundary.

We can implement this in a single loop. We maintain two variables: `left_product` and `right_product`. In each iteration `i`, we update `left_product` with `nums[i]` and `right_product` with `nums[n-1-i]`. If either product becomes zero, we reset it to 1 to start a new subproblem.

```java
class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int maxProduct = nums[0];
        int leftProduct = 1;
        int rightProduct = 1;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // Reset if product becomes 0
            leftProduct = (leftProduct == 0 ? 1 : leftProduct) * nums[i];
            rightProduct = (rightProduct == 0 ? 1 : rightProduct) * nums[n - 1 - i];
            
            maxProduct = Math.max(maxProduct, Math.max(leftProduct, rightProduct));
        }
        return maxProduct;
    }
}
```
### Algorithm
- Initialize `max_product` with the largest element in `nums` to handle edge cases.
- Initialize `left_product = 1` and `right_product = 1`.
- Get the length of the array, `n`.
- Iterate with index `i` from 0 to `n-1`:
- If `left_product` is 0, reset it to 1. Then, update `left_product` by multiplying with `nums[i]`.
- If `right_product` is 0, reset it to 1. Then, update `right_product` by multiplying with `nums[n-1-i]`.
- Update `max_product = max(max_product, left_product, right_product)`.
- Return `max_product`.

## Dynamic Programming with Max and Min Tracking
This approach adapts Kadane's algorithm, which is used for the maximum sum subarray problem. To handle negative numbers, we track both the maximum and minimum product of subarrays ending at the current position.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Constant space complexity O(1).; A standard and powerful dynamic programming pattern that can be adapted to similar problems.
**Cons:** The logic can be slightly more complex to formulate than the brute-force approach.
### Explanation
The standard Kadane's algorithm for maximum sum subarray doesn't work directly because multiplying by a negative number can turn a maximum product into a minimum and vice-versa. For example, a large negative product, when multiplied by another negative number, can become the new maximum positive product.

To solve this, we maintain two variables at each step `i`:
1. `max_so_far`: the maximum product of a subarray ending at `i`.
2. `min_so_far`: the minimum product of a subarray ending at `i`.

When we process the next number `num = nums[i]`, the new `max_so_far` can be one of three values: `num` itself (starting a new subarray), `num * previous_max_so_far`, or `num * previous_min_so_far`. The same logic applies to the new `min_so_far`. We also keep a global `result` variable that is updated with `max_so_far` at each step.

```java
class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = maxSoFar;

        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            
            // Store the old maxSoFar because we need it to calculate the new minSoFar
            int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
            minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));

            maxSoFar = tempMax;

            result = Math.max(maxSoFar, result);
        }

        return result;
    }
}
```
### Algorithm
- If the array is empty, return 0.
- Initialize `max_so_far`, `min_so_far`, and `result` to the first element `nums[0]`.
- Iterate through the array from the second element (`i = 1` to `n-1`):
- Let `current_num = nums[i]`.
- Store the old `max_so_far` in a temporary variable, say `temp_max`, as it's needed for the `min_so_far` calculation.
- The new `max_so_far` is the maximum of `current_num`, `current_num * max_so_far`, and `current_num * min_so_far`.
- The new `min_so_far` is the minimum of `current_num`, `current_num * temp_max`, and `current_num * min_so_far`.
- Update `result = max(result, max_so_far)`.
- Return `result`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaxProduct(int[] nums) {
        int f = nums[0], g = nums[0], ans = nums[0];
        for (int i = 1; i < nums.Length; ++i) {
            int ff = f, gg = g;
            f = Math.Max(nums[i], Math.Max(ff * nums[i], gg * nums[i]));
            g = Math.Min(nums[i], Math.Min(ff * nums[i], gg * nums[i]));
            ans = Math.Max(ans, f);
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int maxProduct(int[] nums) {
    int f = nums[0], g = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; ++i) {
      int ff = f, gg = g;
      f = Math.max(nums[i], Math.max(ff * nums[i], gg * nums[i]));
      g = Math.min(nums[i], Math.min(ff * nums[i], gg * nums[i]));
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var maxProduct = function (
  nums,
) {
  let [f, g, ans] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    const [ff, gg] = [f, g];
    f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
    g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
    ans = Math.max(ans, f);
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  int maxProduct(vector<int> &nums) {
    int f = nums[0], g = nums[0], ans = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      int ff = f, gg = g;
      f = max({nums[i], ff * nums[i], gg * nums[i]});
      g = min({nums[i], ff * nums[i], gg * nums[i]});
      ans = max(ans, f);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int: ans = f = g = nums[0] for x in nums[1:]: ff, gg = f, g f = max(x, ff * x, gg * x) g = min(x, ff * x, gg * x) ans = max(ans, f) return ans

```