【刷题日记】152. 乘积最大子数组

一、题目描述：

今天的每日一天过于简单，咱们还是来做一个考察率高的数组类型的题目吧，152. 乘积最大子数组

二、这道题考察了什么思想？你的思路是什么？

本题题目简明扼要不兜圈子，题目要求我们在给出的整数数组中，找到乘积最大的非空连续子数组，此处的要求很明确

• 结果需要是一个非空的，至少有一个元素的数组
• 结果的数组一定是原数组的连续子序列

分析

题目中给出的数组中，需要咱们从所有非空连续子数组中找到乘积最大的那一组，那么我们来看，一个数组，咱们可以按照数组的顺序来将当前为止的子数组和的最大值记录下来，例如题目中的示例 1

看到这里，我们是不是会认为后一个数字所在子数组的最大乘积是依赖于和上一个数字的最大乘积进行比较，那么一次类推，咱们就可以得到一个递推公式

Fmax(i)=max(Fmax(i−1)∗nums[i],nums[i])Fmax(i) = max(Fmax(i-1) * nums[i], nums[i])Fmax(i)=max(Fmax(i−1)∗nums[i],nums[i])

看样子好像行的通，但是咱们仔细看题目中就可以发现，题目中给出的数组，其实是有正数，有负数的，咱们并不知道数组中的负数有多少个，自然也不知道正数有多少个

对于负数来说，自然是负数遇到和负数相乘是最大的，反之就是最小的了

对于正数来说，自然是正数遇到正数相乘是最大的，反之亦然

那么对于上述的递推公式，咱们知道并不能解决本题的问题，因为 Fmax(i) 他并不一定是站在 Fmax(i-1) 的最优解的基础上进行比较，而是可能是Fmin(i-1) 的基础上进行比较，例如下面例子

咱们应该是需要将，当前位置的值 nums[i] ，当前位置的之前的最大值 Fmax(i-1)*nums[i] ，当前位置的最小值 Fmin(i-1)*nums[i] 进行比较，对应到公式有：

Fmax(i)=max(Fmax(i−1)∗nums[i],max(nums[i],Fmin(i−1)∗nums[i]))Fmax(i)=max(Fmax(i-1)*nums[i], max(nums[i], Fmin(i-1)*nums[i]))Fmax(i)=max(Fmax(i−1)∗nums[i],max(nums[i],Fmin(i−1)∗nums[i]))

Fmin(i)=min(Fmin(i−1)∗nums[i],min(nums[i],Fmax(i−1)∗nums[i]))Fmin(i)=min(Fmin(i-1)*nums[i], min(nums[i], Fmax(i-1)*nums[i]))Fmin(i)=min(Fmin(i−1)∗nums[i],min(nums[i],Fmax(i−1)∗nums[i]))

最后取 Fmax(i) 的最大值即可

如下：

我们必须要考虑负号问题，按照上述表格，咱们实际上从上述原数组中，找到的非空连续子数组的乘积最大是 144

也就是整个原数组全部乘起来得到的结果，这才是正确的

如果是按照最上面的 Fmax 的方式来处理的话，那么 对于原数组索引Wie 4 ，实际值为 -3 的位置上来说，最大值就是 -3，整个数组的结果就是 6 ，这就不正确了

感兴趣的 xdm 可以进行推演一下，还是非常有趣的，接下来咱们就来撸代码实现吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 此处需要注意负号问题，咱们需要将当前位置的的值nums[i] ，上一个位置的最大值*nums[i]，上一个位置的最小值 *num[i] 进行比较
• 由于咱们是遍历数组来进行比较和计算的，后一次计算依赖于上一次计算的结果，因此，咱们就只需要 2 个变量来记录上一次计算的 最大值和最小值即可

编码如下：

func maxProduct(nums []int) int {
    // 初始化当前的最大值和最小值
    res, maxNum, minNum := nums[0], nums[0], nums[0]
    for i,num := range nums {
        if i == 0{
            continue
        }
        // 记录上一次的最大值和最小值
        tmpMax , tmpMin := maxNum, minNum
        // 进行比较
        maxNum = max(tmpMax*num, max(num, num* tmpMin))
        minNum = min(tmpMin*num, min(num, num* tmpMax))
        res = max(maxNum, res)
    }
    return res
}
func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}
func min(a,b int) int {
    if a<b {
        return a
    }
    return b
}
四、总结：

本题的做法，仔细看了上述推演的，我们就知道空间复杂度是 O(1) ，因此咱们引入的都是常数级别的空间消耗

时间复杂度是 O(n) ，因为咱们遍历了一遍题目给出的nums 数组

原题地址：152. 乘积最大子数组

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~