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代码]()