blind-75

Maximum Product Subarray

Best Case: The best case occurs with all positive numbers.
Worst Case: The worst case occurs with a mix of negative numbers and zeros.

Approach:

1. Track maximum and minimum products at each step since multiplying two negatives results in a positive.

Explanation to Interviewer:
“I would maintain both maximum and minimum products at each index because a negative number could turn into a positive product if multiplied with another negative.”

Code Implementation:

JavaScript:

function maxProduct(nums) {
    let maxProd = nums[0], minProd = nums[0], result = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            [maxProd, minProd] = [minProd, maxProd]; // Swap on negative number
        }
        
        maxProd = Math.max(nums[i], maxProd * nums[i]);
        minProd = Math.min(nums[i], minProd * nums[i]);
        
        result = Math.max(result, maxProd);
    }

    return result;
}

const nums = [2,-3,-2,-4];
console.log(maxProduct(nums)); // Output: 48

Python:

def max_product(nums):
    max_prod = min_prod = result = nums[0]

    for num in nums[1:]:
        if num < 0:
            max_prod, min_prod = min_prod, max_prod
            
        max_prod = max(num, max_prod * num)
        min_prod = min(num, min_prod * num)
        
        result = max(result, max_prod)

    return result

nums = [2,-3,-2,-4]
print(max_product(nums)) # Output: 48