2021-10-18：乘积最大子数组。给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。力扣152。
福大大 答案2021-10-18：
动态规划。
情况1.i位置。[i]。
情况2.i位置向左扩。[i]*dp[i-1]。dp[i-1]是最大累乘积。
情况3.i位置向左扩。[i]*dp[i-1]。dp[i-1]是最小累乘积。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{
2, 3, -2, 4}
ret := maxProduct(arr)
fmt.Println(ret)
}
func max(arr []float64) float64 {
if len(arr) == 0 {
return 0 // 报错！
}
n := len(arr)
// 上一步的最大
premax := arr[0]
// 上一步的最小
premin := arr[0]
ans := arr[0]
for i := 1; i < n; i++ {
p1 := arr[i]
p2 := arr[i] * premax
p3 := arr[i] * premin
curmax := math.Max(math.Max(p1, p2), p3)
curmin := math.Min(math.Min(p1, p2), p3)
ans = math.Max(ans, curmax)
premax = curmax
premin = curmin
}
return ans
}
func maxProduct(nums []int) int {
ans := nums[0]
min := nums[0]
max := nums[0]
for i := 1; i < len(nums); i++ {
curmin := getMin(nums[i], getMin(min*nums[i], max*nums[i]))
curmax := getMax(nums[i], getMax(min*nums[i], max*nums[i]))
min = curmin
max = curmax
ans = getMax(ans, max)
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
图片