will的个人博客

因为有负有正，所以不能简单地使用一个dp记录。负数最小乘以负数可能会变最大，正数最大乘以负数可能会变最小。因此还需要记录乘积最小的情况，用于不断更新。

定义状态maxF[i]，表示以i结尾的子数组的最大乘积；定义状态minF[i]，表示表示以i结尾的子数组的最小乘积。

考虑状态转移，maxF[i]可有nums[i]加入maxF或minF转移形成，也有可能由nums[i]转移形成；minF[i]可有nums[i]加入maxF或minF转移形成，也有可能由nums[i]直接形成（子数组的考量）

故状态转移方程为

maxF[i] = max(maxF[i-1]*nums[i], max(minF[i-1]*nums[i], nums[i]) )
minF[i] = min(maxF[i-1]*nums[i], min(minF[i-1]*nums[i], nums[i]) )

初始条件

maxF[0] = nums[0]
minF[0] = nums[0]

遍历顺序是从左往右

因为状态定义是以i结尾的子数组的最大乘积，最终答案可能不以i结尾，所以使用res在遍历过程中更新记录子数组的最大乘积

func maxProduct(nums []int) int {
    maxF, minF := make([]int,len(nums)), make([]int,len(nums))
    maxF[0] = nums[0]
    minF[0] = nums[0]

    res := nums[0]
    for i := 1; i < len(nums); i++ {
        maxF[i] = max(maxF[i-1]*nums[i], max(minF[i-1]*nums[i], nums[i]) )
        minF[i] = min(maxF[i-1]*nums[i], min(minF[i-1]*nums[i], nums[i]) )
        res = max(res, maxF[i])
    }
    return res
}

同时发现maxF[i]和minF[i]只依赖于 i-1 的结果，可以使用滚动数组来压缩空间

func maxProduct(nums []int) int {

    maxF := nums[0]
    minF := nums[0]

    res := nums[0]
    for i := 1; i < len(nums); i++ {
        t := maxF
        maxF = max(maxF*nums[i], max(minF*nums[i], nums[i]) )
        minF = min(t*nums[i], min(minF*nums[i], nums[i]) )
        res = max(res, maxF)
    }
    return res
}