一文看懂《子数组的最大乘积问题》
一文看懂《子数组的最大乘积问题》
这道题出自《编程之美》第二章第 13 小节。
问题描述：给定一个长度为 N 的整数数组，只允许乘法，不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组，并写出算法的时间复杂度。
这道题目和另外一个《连续数组的最大乘积》有点像，那道题我们可以通过记录全局最大值和负数最小值来完成。这道题则稍微有点不同，我们来看一下。
暴力法
最直观的解法是将全部组合找出来，一共是 N 个组合，分别计算他们的乘积， 然后计算最大值，一共有 N 个 N-1 个数字的组合，因此时间复杂度是O(N^2) 。
参考 JavaScript 代码：
function LSP(list) {
let ret = 1;
let max = -Number.MAX_VALUE;
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
if (i !== j) ret *= list[j];
}
max = Math.max(max, ret);
ret = 1;
}
return max;
}
这种方法略显暴力，显然不是一种好的方法，不过作为一种启发， 在面试中先提供一种普通的减法，然后提供思路慢慢优化，会让面试官看到你的 闪光点。
上面的解法产生了大量的重复计算，我们是否可以将重复计算存起来，以减少这种重复计算呢？我们来看下下面的解法。
空间换时间
我们计算 N-1 个元素的乘积，也就是说有一个元素被排除在外。我们假设被排除的 元素索引为 i（0 <= i < N, 且 i 为整数）。
我们用两个数组 l 和 r 分别记录从前和从后的子数组乘积。
我们用 l[i]表示原数组中从 0 开始到 i - 1(包括 i - 1)的乘积， r[i]表示原数组中从 i(包括 i)到 N - 1(包括 N - 1)的乘积。
于是我们只需要一次循环l[i] * r[i + 1]计算出 N - 1 个数字的乘积。
由于只需要 从有到尾和从尾部到头扫描数组两次即可得到数组l和r，进而可以在线性的时间复杂度获取到所有的乘积，然后在这个过程中我们就可以取出最大值，因此这样做的时间复杂度为O(N)。
参考 JavaScript 代码：
function LSP(list) {
let ret = 1;
let max = -Number.MAX_VALUE;
const l = [];
const r = [];
l[0] = 1;
r[0] = 1; // useless
r[list.length] = 1;
for (let i = 1; i < list.length; i++) {
l[i] = l[i - 1] * list[i - 1];
}
for (let i = list.length - 1; i >= 1; i--) {
r[i] = r[i + 1] * list[i];
}
for (let i = 0; i < list.length; i++) {
ret *= l[i] * r[i + 1];
max = Math.max(max, ret);
ret = 1;
}
return max;
}
这种时间复杂度已经很优秀了，接下来我们通过数学分析再来看一下这道题。
数学分析
实际上，总体的乘积一共只有三种情况：正，负和 0。
- 如果是 0，我们进一步找有没有别的 0，有的话返回 0, 没有的话我们就算下除了这个 0 之外所有的乘积，然后取它和 0 的较大值即可。(然而这两个逻辑可以合并)
- 如果是正，那么删除最小的正数即可
- 如果是负数，则说明一定至少有一个负数存在，我们只要知道绝对值最小的负数删除即可
通过上面的分析我们只要遍历一次找出这几个核心遍历，然后再来一次遍历算出乘积（乘积忽略前面计算出的需要忽略的索引）即可。
参考 JavaScript 代码：
function LSP(list) {
let ret = 1;
let smallestPositive = Number.MAX_VALUE;
let smallestPositiveI = -1;
let largestNegative = -Number.MAX_VALUE;
let largestNegativeI = -1;
let firstZeroI = -1;
let missingI = -1;
let productAll = 1;
for (let i = 0; i < list.length; i++) {
productAll *= list[i];
if (list[i] === 0 && firstZeroI === -1) {
firstZeroI = i;
}
if (list[i] > 0 && list[i] < smallestPositive) {
smallestPositive = list[i];
smallestPositiveI = i;
}
if (list[i] < 0 && list[i] > largestNegative) {
largestNegative = list[i];
largestNegativeI = i;
}
}
if (productAll > 0) {
missingI = smallestPositiveI;
} else if (productAll < 0) {
missingI = largestNegativeI;
} else {
missingI = firstZeroI;
}
for (let i = 0; i < list.length; i++) {
if (i !== missingI) ret *= list[i];
}
return firstZeroI === -1 ? ret : Math.max(0, ret);
}
这个解法的时间复杂度同样也是O(N)，但是空间复杂度降低到了O(1)。
上面的解法我们判断正负直接粗暴的将所有数字乘了起来，这其实有溢出的风险， 其实我们可以使用别的方法来计算正负，聪明的你肯定已经想到了。
我们可以通过统计正数，负数和0的个数来判断乘积的正负。
总结
子数组乘积问题有很多变种问题，今天我们讲的就是其中一中类型， 我们先通过朴素的解法，然后一步步分析问题的本质，通过空间换时间的解法 进一步减少了时间复杂度。最后我们通过数学分析，进行分类讨论，通过常数的空间复杂度和 线性的时间复杂度解决了问题。
相信大家在面试中如果通过上面的思考过程，一步一步，循循渐进，不仅可以逐步减少自己的紧张， 还能让面试官看到你的思考过程，祝大家找到自己理想的工作。本文完～
腾讯云开发者
