152. Maximum Product Subarray

Problem

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

Example 1:

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

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Problem Summary

Given an integer array nums, find the contiguous subsequence within the sequence that has the largest product (the sequence must contain at least one number).

Solution Approach

• Given an array, find the maximum product of contiguous elements in this array.
• This is a DP problem. The state transition equations are: the maximum value is Max(f(n)) = Max( Max(f(n-1)) * n, Min(f(n-1)) * n); the minimum value is Min(f(n)) = Min( Max(f(n-1)) * n, Min(f(n-1)) * n). As long as these two values are maintained dynamically, if the last number is negative, the maximum value is produced from negative number * minimum value; if the last number is positive, the maximum value is produced from positive number * maximum value.

Code

package leetcode

func maxProduct(nums []int) int {
	minimum, maximum, res := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] < 0 {
			maximum, minimum = minimum, maximum
		}
		maximum = max(nums[i], maximum*nums[i])
		minimum = min(nums[i], minimum*nums[i])
		res = max(res, maximum)
	}
	return res
}