Leetcode 152 穷举法时间超时
来源：1-5 大厂面试为什么总考算法？
甲骨文_0001
2022-10-31
/**
* @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循环就好了，没看太懂。。。。
写回答
1回答
-
liuyubobobo
2022-10-31
首先，乘积最大的连续子数组内一定不能有 0。一旦有 0，乘积归 0。所以先将整个数组划分成不包含 0 的若干段，处理每一段，看在每一段上得到的最大乘积是多少。
下面，我们面对一个数组，这个数组中不包含 0，其能获得的最大的连续的乘积是多少？
有如下结论：最大的连续乘积所对应的子数组，或者是这个数组的一个前缀，或者是这个数组的一个后缀，而不可能是这个数组的中间一段。
为什么？我们可以用反证法来看：
假设这个数组的最大乘积对应的连续数组，既不是前缀，又不是后缀，是中间的一段。那么这段子数组前面也有元素，后面也有元素。
首先，这个子数组前后的元素都不可能为正数。因为如果是正数，肯定可以把这个正数包含进来，形成一个乘积更大的子数组。
那么，这个子数组前后就只有可能都是负数。但如果前后都是负数，我们就可以把这两个负数都包含进来，负负得正，形成一个乘积更大的子数组。
不管怎样都矛盾。所以，这个子数组不可能是中间的一段，只能或者是一个前缀，或者是一个后缀。
我们可以枚举一个数组的所有前缀和所有后缀的乘积，找最大的，复杂度是 O(n) 的。
继续加油！：）
132022-10-31
相似问题