这道题出自《编程之美》第二章第 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的个数来判断乘积的正负。

总结

子数组乘积问题有很多变种问题，今天我们讲的就是其中一中类型， 我们先通过朴素的解法，然后一步步分析问题的本质，通过空间换时间的解法 进一步减少了时间复杂度。最后我们通过数学分析，进行分类讨论，通过常数的空间复杂度和 线性的时间复杂度解决了问题。

相信大家在面试中如果通过上面的思考过程，一步一步，循循渐进，不仅可以逐步减少自己的紧张， 还能让面试官看到你的思考过程，祝大家找到自己理想的工作。本文完～