乘积最大子数组
给你一个整数数组 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