[Leetcode] – Maximum Product Subarray Solution

626

In the given problem statement, we have an array of integers and we need to find the maximum product possible for a contiguous subarray.

The most important part of this problem is that the elements have to be contiguous. So special attention needs to be given for negative numbers and zeroes.

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

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

Brute Force Solution

The brute force approach to finding the maximum product subarray involves checking all possible subarrays and calculating their products to find the maximum product.

1. Initialize a variable max_product to store the maximum product, initially set to the minimum possible value.
2. Iterate through all possible starting indices of the subarray.
3. For each starting index, iterate through all possible ending indices greater than or equal to the starting index.
4. Extract the subarray from the starting index to the ending index.
5. Calculate the product of all elements in the subarray.
6. Update max_product if the calculated product is greater than the current maximum.
7. Repeat steps 3-6 until all possible subarrays are considered.
8. Return max_product as the maximum product of a subarray within the given array.

This brute force approach has a time complexity of O(n^3), where n is the length of the input array. Since it involves nested loops, it checks every possible subarray combination, making it highly inefficient for large input sizes.

While the brute force solution is straightforward, it is not efficient for solving larger instances of the problem. We need something better.

Efficient Solution

To solve this problem, you can utilize the dynamic programming approach. Here’s a general outline of the solution:

1. Initialize two variables, max_product and min_product, both set to the first element of the array.
2. Initialize a variable max_global to store the overall maximum product.
3. Iterate through the array starting from the second element.
4. For each element, update max_product and min_product by considering three possibilities: a. Multiply the current element by max_product (to include the current element in the positive product chain). b. Multiply the current element by min_product (to include the current element in the negative product chain, in case the current element is negative). c. Start a new subarray from the current element (if the previous subarray’s product is not significant).
5. Update max_global by comparing it with max_product.
6. Repeat steps 4-5 until all elements are processed.
7. Return max_global as the maximum product of a subarray within the given array.

This approach allows you to keep track of both the maximum and minimum product at each step, considering the possibility of negative numbers and the potential of changing the product’s sign.

Code

  int maxProduct(int[] nums) {

    int n = nums.length;
    int leftProduct = 1;
    int rightProduct = 1;
    int ans = nums[0];

    for (int i = 0; i < n; i++) {

      //if any of leftProduct or rightProduct become 0 then update it to 1
      leftProduct = leftProduct == 0 ? 1 : leftProduct;
      rightProduct = rightProduct == 0 ? 1 : rightProduct;

      //prefix product
      leftProduct *= nums[i];

      //suffix product
      rightProduct *= nums[n - 1 - i];

      ans = Math.max(ans, Math.max(leftProduct, rightProduct));
    }

    return ans;
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

Video Explanation