前言：
此刻你们对“子数组最大值和最小值乘积的最大值”可能比较着重，我们都需要知道一些“子数组最大值和最小值乘积的最大值”的相关资讯。那么小编也在网络上收集了一些对于“子数组最大值和最小值乘积的最大值””的相关资讯，希望朋友们能喜欢，小伙伴们一起来了解一下吧！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 mainimport ( "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 }}执行结果如下：
***
[左神java代码]()
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #子数组最大值和最小值乘积的最大值
