Leetcode 152 穷举法时间超时

Question

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let arr = []; // 存放所有连续子数组的乘积

    // nums是否包含有0, 说明乘积肯定有0
    if( nums.includes(0) ){
        arr.push(0); 
    }

    for( let i = 0; i < nums.length; i ++ ){
        if( nums[i] == 0 ){
            continue;
        }
        for( let j = i; j < nums.length; j ++ ){
            if( nums[j] == 0 ){
                break;
            }
            let product = 1;
            // 连续子数组的乘积
            for( let k = i; k <= j; k ++ ){
                product *= nums[k];
            } // for k
            arr.push(product);
        } // for j
    } // for i

    arr.sort((a, b)=>b-a); // 从大到小排序
    return arr[0];
};

老师，这道题目面试的时候我碰上了，我给出了如上的穷举法，起码是通过了考查。但是在leetcode的用例规模下，超时了，我有看您的答案，只是用了一遍for循环就好了，没看太懂。。。。

Answer 1

liuyubobobo 2022-10-31 16:03:21

首先，乘积最大的连续子数组内一定不能有 0。一旦有 0，乘积归 0。所以先将整个数组划分成不包含 0 的若干段，处理每一段，看在每一段上得到的最大乘积是多少。

下面，我们面对一个数组，这个数组中不包含 0，其能获得的最大的连续的乘积是多少？

有如下结论：最大的连续乘积所对应的子数组，或者是这个数组的一个前缀，或者是这个数组的一个后缀，而不可能是这个数组的中间一段。

为什么？我们可以用反证法来看：

假设这个数组的最大乘积对应的连续数组，既不是前缀，又不是后缀，是中间的一段。那么这段子数组前面也有元素，后面也有元素。

首先，这个子数组前后的元素都不可能为正数。因为如果是正数，肯定可以把这个正数包含进来，形成一个乘积更大的子数组。

那么，这个子数组前后就只有可能都是负数。但如果前后都是负数，我们就可以把这两个负数都包含进来，负负得正，形成一个乘积更大的子数组。

不管怎样都矛盾。所以，这个子数组不可能是中间的一段，只能或者是一个前缀，或者是一个后缀。

我们可以枚举一个数组的所有前缀和所有后缀的乘积，找最大的，复杂度是 O(n) 的。

继续加油！：）

• 提问者 甲骨文_0001 #1

  嗯嗯 谢谢老师：）就是这个结论我之前不知道，所以看您的代码就没看明白：）

• liuyubobobo 回复 提问者 甲骨文_0001 #2

  其实在我看来，更直观的想法是这样的。一个不包含 0 的数组中，最大连续乘积是多少？关键是这个数组中有多少个负数。假设有 x 个负数。如果 x 是偶数，那么直接把整个数组的数字都乘起来就好；关键是如果 x 是奇数的话，那么结果或者是从头向尾乘到到达第 x 个负数为止（包含了 x - 1 个负数），或者从尾向头乘到第 x 个负数为止（包含了 x - 1 个负数），取最大值。
  
  上面这个思路我觉得其实更直观。但具体实现的时候，还是可以同样用求前后缀的方式去实现，就不用数数组中到底有多少个负数了：）

• 提问者 甲骨文_0001 #3

  嗯嗯 您讲完 我自己清晰多了，谢谢老师：）