题目
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
题目
求连续子数组乘积最大的值
例子
Input: [-2,3,-4]
Output: 24
题解
使用动态规划DP
- ==有子数组的问题很适合使用动态规划来做==
- 求状态转移方程，设maxF(i)表示以i结尾的子数组最大乘积，则有maxF(i)=Max(maxF(i-1)*nums[i],nums[i])
- 但是这里是求乘积，所以必须考虑==负负得正的问题==，即可能原本负数最小值，在剩以一个负数后变为最大值，所以必须保存最小值，同理，原本最大值也可能剩以一个负数变为最小值，所以最大值就必须在最大值剩余当前值，最小值乘以当前值，当前值之间求，最小值同理，然后再用最大值与全局最大值进行比较。得出以下公式
maxF_i = Max(Max(maxF_{i-1}*nums[i],minF_{i-1}*nums[i]),nums[i])
minF_i = Min(Min(minF_{i-1}*nums[i],maxF_{i-1}*nums[i]),nums[i])
globalMax = Max(maxF,globalMax)
代码
func maxProduct(nums []int) int {
L := len(nums)
if L==0{
return 0
}
max := nums[0]
min := nums[0]
globalMax := nums[0]
for i:=1;i<L;i++{
premax := max
max = Max(Max(max*nums[i],nums[i]),min*nums[i])
min = Min(Min(min*nums[i],nums[i]),premax*nums[i])
globalMax = Max(max,globalMax)
}
return globalMax
}
func Max(m1,m2 int)int{
if m1>m2{
return m1
}else{
return m2
}
}
func Min(m1,m2 int)int{
if m1>m2{
return m2
}else{
return m1
}
}
总结
求子数组乘积最大值，理清楚负负得正使得原本最小值变为最大值的情况很重要。
关于求==子数组的问题可以考虑使用动态规划的思路来==做，求子数组和的问题也可以用动态规划。
