Blind 75 - problem 6 : Maximum Product Subarray

Problem Statement

Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product and return its product.

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 is 0 because the subarray [0] has the largest product.

---

Optimal Approach

The optimal solution for this problem is to use dynamic programming with two variables, maxProd and minProd, to keep track of the maximum and minimum product ending at each position. This is crucial because a negative number can turn the smallest product into the largest product if multiplied with another negative number.

We process each number in the array, and for each number, we update both the maxProd and minProd. This allows us to efficiently compute the maximum product subarray in O(n) time.

---

LeetCode-Compatible Code Implementations

C++ Solution (Optimal Approach)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxProd = nums[0], minProd = nums[0], result = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < 0) {
                swap(maxProd, minProd); // Swap if the current number is negative
            }
            
            maxProd = max(nums[i], maxProd * nums[i]); // Update maxProd
            minProd = min(nums[i], minProd * nums[i]); // Update minProd
            
            result = max(result, maxProd); // Update the result with the maximum product found
        }
        
        return result;
    }
};

Regular C++ Solution with Use Cases

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProduct(vector<int>& nums) {
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) {
            swap(maxProd, minProd); // Swap if the current number is negative
        }
        
        maxProd = max(nums[i], maxProd * nums[i]); // Update maxProd
        minProd = min(nums[i], minProd * nums[i]); // Update minProd
        
        result = max(result, maxProd); // Update the result with the maximum product found
    }
    
    return result;
}

int main() {
    vector<int> nums = [2, 3, -2, 4];
    cout << "Maximum Product Subarray: " << maxProduct(nums) << endl;
    return 0;
}

---

Step-by-Step Explanation of Code

1. Initialization:

   • maxProd: The maximum product subarray ending at the current index.
   • minProd: The minimum product subarray ending at the current index.
   • result: The global maximum product found so far.

2. Iteration:

   • For each element in the array, if the current element is negative, we swap the maxProd and minProd because multiplying a negative number can turn the smallest product into the largest one.
   • After swapping (if necessary), we update maxProd and minProd by considering two options:
     • The current element alone.
     • The current element multiplied by the existing maxProd or minProd.
   • After updating maxProd and minProd, we update result to store the largest product found so far.

3. Final Output:

   • After iterating through the array, result contains the largest product subarray.

---

Dry Run / Execution Steps

Input: [2, 3, -2, 4]

1. Initialization:

   • maxProd = 2
   • minProd = 2
   • result = 2

2. Iteration:

   • i = 1 (nums[1] = 3):
     • maxProd = max(3, 2 * 3) = 6
     • minProd = min(3, 2 * 3) = 3
     • result = max(2, 6) = 6
   • i = 2 (nums[2] = -2):
     • Swap maxProd and minProd: maxProd = 3, minProd = 6
     • maxProd = max(-2, 3 * -2) = -6
     • minProd = min(-2, 6 * -2) = -12
     • result = max(6, -6) = 6
   • i = 3 (nums[3] = 4):
     • maxProd = max(4, -6 * 4) = 4
     • minProd = min(4, -12 * 4) = -48
     • result = max(6, 4) = 6

Output: 6

---

Alternative Approaches & Why Not?

1. Brute Force Approach

• Description: Check all possible subarrays and compute their products.
• Time Complexity: O(n^2) due to nested loops.
• Space Complexity: O(1).

Why Not?: This approach is inefficient for large arrays because it requires checking all possible subarrays, leading to an O(n^2) time complexity.

2. Dynamic Programming (DP) with One Array

• Description: Use a single array to track the maximum and minimum products.
• Time Complexity: O(n).
• Space Complexity: O(n).

Why Not?: While this approach reduces time complexity to O(n), it still requires extra space to store the product values for each index.

---

Best Solution & Why It’s Best

Optimal Solution with Kadane's Algorithm

• Time Complexity: O(n), where n is the number of elements in the array. We only need to iterate through the array once.
• Space Complexity: O(1), as we only use a few variables to track the results.

Kadane’s Algorithm is the best solution for this problem as it is both time-efficient and space-efficient. It efficiently handles the case where a negative number flips the product, and it keeps track of both the maximum and minimum products simultaneously.

Comparison Table:

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2)	O(1)
DP with One Array	O(n)	O(n)
Kadane’s Algorithm (Best)	O(n)	O(1)

---

Complexity Analysis

• Brute Force:

  • Time Complexity: O(n^2) because of the nested loops.
  • Space Complexity: O(1).

• DP with One Array:

  • Time Complexity: O(n), since we traverse the array once.
  • Space Complexity: O(n), as we store the product values in an array.

• Kadane's Algorithm:

  • Time Complexity: O(n) for a single pass through the array.
  • Space Complexity: O(1).

---

Conclusion

Kadane’s Algorithm is the most efficient solution for solving the "Maximum Product Subarray" problem due to its linear time complexity and constant space complexity. It handles negative values effectively and ensures the optimal result with minimal computational overhead.

For similar problems, you can practice with the following:

• LeetCode - Best Time to Buy and Sell Stock.
• LeetCode - House Robber.