给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续,笔者首先想到的就是滑动窗口,但是这里比较特殊,我们不能仅仅维护一个最大值,因此最小值(比如-20)乘以一个比较小的数(比如-10) 可能就会很大。 因此这种思路并不方便。

首先来暴力求解我们使用两层循环来枚举所有可能项,这种解法 的时间复杂度是 O(n^2) 代码如下:

前面说了最小值(比如-20)乘以一个比较小的数(比如-10)可能就会很大 。因此我们需要同时记录乘积最大值和乘积最小值,然后比较元素和这两个的乘积,去不断更新最大值。当然,我们也可以选择只取当前元素。因此实际上我们的选择有三种,而如何选择就取决于哪个选择带来的价值最大(乘积最大或者最小)。

这种思路的解法由于只需要遍历一次,其时间复杂度是 O(n),代码见下方代码区。

当我们知道动态转移方程的时候,其实应该发现了。我们的 dp[i] 只和 dp[i - 1]有关,这是一个空间优化的信号,告诉我们可以借助两个额外变量记录即可。