# 152.M 乘积最大子数组

> Problem: [152. 乘积最大子数组](https://leetcode.cn/problems/maximum-product-subarray/description/)

## 思路

动态规划

设`minDp[i]`表示以`i`为结尾元素的子数组的最大乘积，`maxDp[i]`表示以`i`为结尾元素的子数组的最大乘积，则有：

```
minDp[i] = min(nums[i], min(minDp[i-1]*nums[i], maxDp[i-1]*nums[i])) //元素本身，或者与前一项的最大或最小值之积的最小值
maxDp[i] = max(nums[i], max(minDp[i-1]*nums[i], maxDp[i-1]*nums[i])) //元素本身，或者与前一项的最大或最小值之积的最大值
```

## Code

```go
func maxProduct(nums []int) int {
	minDp := make([]int, len(nums))
	maxDp := make([]int, len(nums))
	minDp[0] = nums[0]
	maxDp[0] = nums[0]
	ans := maxDp[0]
	for i := 1; i < len(nums); i++ {
		// 如果nums[i]为负数，最大值来自于minDp[i-1]*nums[i]
		minDp[i] = min(nums[i], min(minDp[i-1]*nums[i], maxDp[i-1]*nums[i]))
		maxDp[i] = max(nums[i], max(minDp[i-1]*nums[i], maxDp[i-1]*nums[i]))
		ans = max(ans, maxDp[i])
	}

	return ans
}

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

	return b
}

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

	return b
}
```

由于每次计算都只依赖前一项的min和max，因此可以对空间进行优化：

```go
func maxProduct(nums []int) int {
	preMin := nums[0]
	preMax := nums[0]
	ans := preMin
	for i := 1; i < len(nums); i++ {
		// 如果nums[i]为负数，最大值来自于minDp[i-1]*nums[i]
		if nums[i] < 0 {
			preMin, preMax = preMax, preMin
		}
		preMin = min(preMin*nums[i], nums[i])
		preMax = max(preMax*nums[i], nums[i])
		ans = max(ans, preMax)
	}

	return ans
}
```