Code Implementation

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0
        max_prod = min_prod = result = nums[0]
        for i in range(1, len(nums)):
            choices = (nums[i], max_prod * nums[i], min_prod * nums[i])
            max_prod = max(choices)
            min_prod = min(choices)
            result = max(result, max_prod)
        return result
      

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxProd = nums[0], minProd = nums[0], result = nums[0];
        for (size_t i = 1; i < nums.size(); ++i) {
            int curr = nums[i];
            int tempMax = max({curr, maxProd * curr, minProd * curr});
            int tempMin = min({curr, maxProd * curr, minProd * curr});
            maxProd = tempMax;
            minProd = tempMin;
            result = max(result, maxProd);
        }
        return result;
    }
};
      

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxProd = nums[0], minProd = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            int tempMax = Math.max(curr, Math.max(maxProd * curr, minProd * curr));
            int tempMin = Math.min(curr, Math.min(maxProd * curr, minProd * curr));
            maxProd = tempMax;
            minProd = tempMin;
            result = Math.max(result, maxProd);
        }
        return result;
    }
}
      

var maxProduct = function(nums) {
    if (!nums || nums.length === 0) return 0;
    let maxProd = nums[0], minProd = nums[0], result = nums[0];
    for (let i = 1; i < nums.length; i++) {
        let curr = nums[i];
        let tempMax = Math.max(curr, maxProd * curr, minProd * curr);
        let tempMin = Math.min(curr, maxProd * curr, minProd * curr);
        maxProd = tempMax;
        minProd = tempMin;
        result = Math.max(result, maxProd);
    }
    return result;
};
      

Problem Description

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

• The subarray must be contiguous (elements are consecutive in the original array).
• You may assume at least one number is present in nums.
• Negative numbers and zeros are allowed in the array.
• Return the largest product possible from any such subarray.

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

Thought Process

At first glance, this problem looks similar to the classic "Maximum Subarray Sum" problem, but instead of sums, we are dealing with products. The brute-force approach would be to consider every possible subarray, calculate its product, and keep track of the maximum. However, this would be very inefficient for large arrays.

The twist with products is that multiplying by a negative number can flip a large positive product into a negative one, and vice versa. Zeros also reset the product. This means that unlike sums, we can't just keep a running product; we need to track both the maximum and minimum products ending at each position, because a minimum (negative) product could become the maximum if multiplied by a negative number later on.

The key insight is to keep track of two things at each step:

• The maximum product ending at the current position.
• The minimum product ending at the current position.

Solution Approach

Let's break down the optimized solution step by step:

1. Initialize: Start by setting both max_prod and min_prod to the first element of nums. Also, keep a result variable to track the global maximum product found so far.
2. Iterate through the array: For each element from the second to the last:
   • Compute the possible products at this position: the current number itself, the current number times the previous max_prod, and the current number times the previous min_prod.
   • The new max_prod is the maximum of these three values.
   • The new min_prod is the minimum of these three values.
   • Update result if max_prod is greater than the current result.
3. Return the result: After traversing the array, result holds the largest product of any contiguous subarray.

This approach only requires a single pass through the array and constant extra space, making it very efficient.

Example Walkthrough

Let's walk through the input nums = [2, 3, -2, 4] step by step:

• Initialize: max_prod = 2, min_prod = 2, result = 2
• i = 1 (nums[1] = 3):
  • Choices: 3, 2*3=6, 2*3=6
  • max_prod = max(3,6,6) = 6
  • min_prod = min(3,6,6) = 3
  • result = max(2,6) = 6
• i = 2 (nums[2] = -2):
  • Choices: -2, 6*-2=-12, 3*-2=-6
  • max_prod = max(-2,-12,-6) = -2
  • min_prod = min(-2,-12,-6) = -12
  • result = max(6,-2) = 6
• i = 3 (nums[3] = 4):
  • Choices: 4, -2*4=-8, -12*4=-48
  • max_prod = max(4,-8,-48) = 4
  • min_prod = min(4,-8,-48) = -48
  • result = max(6,4) = 6

The largest product found is 6, which comes from the subarray [2,3].

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) — For every possible subarray, calculate its product.
  • Space Complexity: O(1) — Only a few variables needed.
• Optimized approach (as above):
  • Time Complexity: O(n) — Only a single pass through the array is needed.
  • Space Complexity: O(1) — Only a constant number of variables are used.

The optimized algorithm is much faster and suitable for large arrays.

Summary

The Maximum Product Subarray problem requires careful handling of negative numbers and zeros, since they can dramatically change the product. By keeping track of both the maximum and minimum products ending at each position, we can efficiently find the largest possible product in a single pass. This dynamic programming approach is elegant, fast, and easy to implement.