乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
题解思路
如果按照常规动态规划解法，维护一个dp数组记录以nums中每个元素为结尾的乘积最大连续子数组的乘积，会出现错误，因为如果考虑[-2, 3, -4]这样的用例，会发现按照上述方法的答案为3，而正确结果应该为-2 * 3 * -4 = 24. 因为当前位置的最优解未必是由前一个位置的最优解转移得到的。
当 前一个位置是一个很小的负数时，如果当前元素也是负数，那么就可以得到一个很大的值，而这个值很可能就是我们要找的解。而在上一段提到的方法中，这个解被忽略掉了。
考虑到一个绝对值很大的负数也是有利用价值的，我们应该同时维护一个dp数组来存储以nums中某个元素为结尾的子串的乘积的最小值。而以当前元素为结尾的连续子序列的乘积的最大值，可以是
当前元素 * 以上一个元素为结尾的最长子序列的乘积的最大值 亦可以是
当前元素 * 以上一个元素为结尾的最长子序列的乘积的最小值
两种情况分别对应当前元素为正和为负的情况。
状态转移方程可以写成：
代码
func maxProduct(nums []int) int {
// maxF和minF来维护加上当前元素的最大和最小值
maxF, minF := nums[0], nums[0]
result := -0x80000000
result = findMax(maxF,result)
for i:= 1; i< len(nums); i++ {
ma, mi := maxF,minF
maxF = findMax(ma * nums[i], findMax(mi * nums[i], nums[i]))
minF = findMin(ma * nums[i], findMin(mi * nums[i], nums[i]))
result = findMax(maxF, result)
}
return result
}
func findMax(a int, b int) int {
if a > b {
return a
}else{
return b
}
}
func findMin(a int, b int) int {
if a < b {
return a
}else{
return b
}
}
性能：
执行用时：8 ms, 在所有 Go 提交中击败了33.84%的用户
内存消耗：3.2 MB, 在所有 Go 提交中击败了43.59%的用户
通过测试用例：190 / 190