[LeetCode] Maximum Product Subarray的两种思路

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

1）注意这里的数组是整型的，如果含有浮点数，就有可能出现0-1之间类似0.25这样的小数，所以即使是全都是正数，也可以越乘越小。如果数组里的数字全为正数还好说，因为可以用求对数的方式把求乘积转化为求和，从而转换为之前的Maximum Subarray。但是因为这题有负数和0的存在，所以求对数的方法行不通。

2）这题的测试用例里数组元素的绝对值都非常的小，而实际中如果真的连乘起来，最后数值越界很容易发生的。如果考虑这一点，要么估计得用类似Java里BigInteger类这样的东西去避免越界。

言归正传，这题我觉得至少有两种思路求解。

思路一：类似Maximum Subarray的解题思路，在遍历过程中，不断更新以当前元素为终点的subarray的乘积极大值（下面简称极大值）和最大值。本质上无非就是要做出一个二选一：要么继续把当前遍历的元素算上，扩展当前的subarray，要么就重新开始一个subarray。此外，如何更新最大值？由于有整数，负数和0的存在，需要分为三种情况，并且还需要维护一个极小值。为了方便连乘操作，这里规定维护的最大乘积必须大于等于1，即不能等于0。另外需要注意，在没有遍历到负数之前，极小值这里其实和极大值是一样大的（不考虑为0的情况），也可以是正数。

综合考虑如下：

1）如果当前元素为正数，那么极大值只可能扩大，所以应该继续扩展当前subarray：

此种情况简单，极大值应该更新为原极大值乘以当前元素，极小值更新为原极小值乘以当前元素。全局最大值跟极大值比较。

2）如果当前元素为负数，那么极大值可能会变小，所以不清楚应该继续扩展当前subarray还是新起一个subarray：

对于极大值的更新：如果扩展当前subarray，极大值为原极小值乘以当前元素；如果另外新起一个subarray，由于当前元素为负数，所以直接舍弃，根据规定，设为初始值1。由于这里原极小值不一定为负数，所以前者和后者之间比较没有绝对的谁大。

对于极小值的更新：如果扩展当前subarray，极小值为原极大值乘以当前元素；如果另外新起一个subarray，极小值为当前元素。不过由于之前极大值肯定大于1，所以前者肯定比后者大，所以极小值更新为原极大值乘以当前元素。

最应该小心的地方是更新全局最大值：这里的全局最大值不能和极大值比较，而应该和极小值乘以当前元素值比较，即扩展当前subarray的选择比较。因为如果极大值此时为1，则并不是靠实实在在存在的，以当前元素结尾的subarray获得，而是靠舍弃当前元素，寄希望于之后“可能”出现的新subarray。举个例子，如果数组为{-2}，或者{-1, 0, -2}，那么无论如何是不会出现最大值为1这种情况的，因为负数的后面没有出现过正数。

3）如果当前元素为0，那么包括一个0会使得极大值成为0，而按照操作规定，这里的极大值应该大于等于1，所以应该舍弃当前元素，新起一个subarray。

对于极大值和极小值，由于新起一个subarray，全部还原为1。

对于全局最大值的更新，这里和2）类似。由于极大值的获取是寄希望于之后“可能”出现的新subarray，所以更新全局最大值的时候不能和此时的极大值1进行比较，而应该和实实在在的0比较。

以下代码，loc_min和loc_max表示极小值和极大值，glb_max为所求。

思路二：如果数组里面没有0，这题可以得到大大简化，所以我们可以先考虑如何处理一个不含0的数组。如此一来，不管怎么乘，绝对值都会增长，所以最重要的就是要保证最后的乘积为正数。因此，可以分为两种情况讨论：

1）如果数组内负数的个数为偶数，直接包括整个数组即可，最大乘积就是整个数组元素的乘积。

2）如果数组内负数的个数为奇数，则应该丢弃一个含有一个奇数的部分。为了使得所剩的数组最大限度的连续，无非就是两种情况：

2.1) 丢弃掉数组里出现的第一个负数和在它之前的元素。例如{1, 2, -3, 4, -5, 6, 7}，由于第一个负数为-3，丢弃最开始的1,2和-3。

2.2) 丢弃掉数组里出现的最后一个负数和在它之后的元素。用上个例子，由于最后一个负数为-5，丢弃最后的-5,6和7。

现在有了对这个题目简化版的解法，如果扩展到这题的解法呢？很简单，首先扫一遍数组，以0为边界，将整个数组分为若干个不含0的subarray，对于每个subarray逐一求解，并求得它们的最大值。另外，由于每个subarray的最大值可能都是负数，所以一旦有0出现，还应该和0比较。代码如下，start表示subarray的起始下标，为-1的时候表示正在寻找下一个subarray。

这种解法比较繁琐，而且由于为了思路清晰，这里我对数组进行了多次扫描，其实可以将循环合并。不过无所谓了，O(n)的时间复杂度不会因为多扫了一两遍而变化。

比较这两种解法，第一种适用性更广，其实对浮点数也同样适用，而第二种则不能允许有0-1之间的小数。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠