Maximum Product Subarray

1. Problem Description

Given an integer array nums, find the contiguous subarray with the largest product (the subarray contains at least one number) and return that product.

2. Approach

1. Approach 1
   • Brute force
   • Use two nested for loops to calculate the maximum product
2. Approach 2
   • Similar to Maximum Subarray, but negative numbers must be considered. Because a negative number can turn the maximum into the minimum and the minimum into the maximum, the current minimum value imin also needs to be maintained

3. Implementation

3.1. Brute Force

func maxProduct(nums []int) int {
	max := math.MinInt32
	for i := 0; i < len(nums); i++ {
		res := 1
		for j := i; j < len(nums); j++ {
			res *= nums[j]
			max = Max(max, res)
		}
	}

	return max
}

3.2. Trial

func maxProduct(nums []int) int {
    res := nums[0]
    minVal := 1
    maxVal := 1
    for _, num := range nums {
        if num < 0 {
            maxVal,minVal = minVal,maxVal
        }
        maxVal = max(maxVal*num, num)
        minVal = min(minVal*num, num)
        res = max(maxVal, res)
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• 152. Maximum Product Subarray - LeetCode
• Backtracking (recursion) and dynamic programming solutions for Maximum Product Subarray
• Visual solution for 152. Maximum Product Subarray