2021-10-18：乘积最大子数组。给你一个整数数组 nums

原创

福大大架构师每日一题

修改于 2021-10-19 09:56:55

2890

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

福大大答案2021-10-18：

动态规划。

情况1.i位置。i。

情况2.i位置向左扩。i*dpi-1。dpi-1是最大累乘积。

情况3.i位置向左扩。i*dpi-1。dpi-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
    }
}

执行结果如下：