2021-10-18：乘积最大子数组。给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。力扣152。

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

    }

}

执行结果如下：
图片

左神java代码

2021-10-18：乘积最大子数组。给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。力扣152。的相关教程结束。