求连续最大子序列积 - leetcode. 152 Maximum Product Subarray
2015-08-26 14:33:00 浏览：1985 作者：管理员
题目链接：Maximum Product Subarray solutions同步在github
题目很简单，给一个数组，求一个连续的子数组，使得数组元素之积最大。这是求连续最大子序列和的加强版，我们可以先看看求连续最大子序列和的题目maximum-subarray，这题不难，我们举个例子。
假设数组[1, 2, -4, 5, -1, 10]，前两个相加后得到3，更新最大值（为3），然后再加上-4后，和变成-1了，这时我们发现如果-1去加上5，不如舍弃前面相加的sum，5单独重新开始继续往后相加。没错，维护一个当前的和，小于0后置为0重新开始就可以了：
var maxSubArray = function(nums) { var maxn = -Infinity; var sum = 0; nums.forEach(function(item) { sum += item; if (sum > maxn) maxn = sum; if (sum < 0) sum = 0; }); return maxn;};接着回到这道题。连续积的复杂之处在于有正负数，如果全是正数，那就好办了，跟最大和差不多，一直相乘，维护个乘积，如果积小于1了，就置为1，因为一个小于1的正数乘以a肯定小于a。但是，理想是美好的，现实是残酷的，我们有负数，那咋办？在维护最大乘积同时维护一个最小的乘积（负数）。
怎么说？举个例子，求数组[-2, -1, -3, 3]的最大连续子序列积，当进行到第一项的时候，我们得到了积-2，我们需要保存这个-2，因为如果-2之后能遇到负数，那么负负得正就可能刷新最大积的值。于是我们得维护两个值，一个大于1的当前最大乘积（res），和一个小于0的最小乘积（tmp）。下一次迭代的res可能由前一次的res乘以一个正数得到，也可能由前一个的tmp乘以负数得到，tmp亦然。
代码很简单，但是重要的是思考的过程。
var maxProduct = function(nums) { var ans = -Infinity , res = 1 , tmp = 1; nums.forEach(function(item) { var _res = res * item , _tmp = tmp * item; ans = Math.max(ans, _res, _tmp); res = Math.max(_res, _tmp, 1); tmp = Math.min(_res, _tmp, 1); }); return ans;};
