Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array 1)注意这里的数组是整型的,如果含有浮点数,就有可能出现0-1之间类似0.25这样的小数,所以即使是全都是正数,也可以越乘越小。如果数组里的数字全为正数还好说,因为可以用求对数的方式把求乘积转化为求和,从而转换为之前的Maximum Subarray。但是因为这题有负数和0的存在,所以求对数的方法行不通。 2)这题的测试用例里数组元素的绝对值都非常的小,而实际中如果真的连乘起来,最后数值越界很容易发生的。如果考虑这一点,要么估计得用类似Java里BigInteger类这样的东西去避免越界。 这题我一共尝试了4种解法。 解法1——基于数学分析的解法 类似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为所求。 解法2——朴素的DP解法 其实以上的解法本质上是一种DP的解法,不过以上解法太过于注重细节上的分析,所以代码看起来比较繁琐。由于负数的存在,需要同时保存当前最大值和当前最小值,所以需要维护两个DP表,可以分别表示为dp_min和dp_max。所以即为dp_max里的最大值。 有时候做题目应该有一种大局观,从细节中解脱出来。这点类似于做物理题时,不一定非要用动力学原理弄清整个过程和每个细节,有时候用简单的从功和能的角度,只关注最终状态也可以顺利解题。这题里需要维护的当前最大值和当前最小值,都是在dp_min[i-1] * A[i],dp_max[i] * A[i],和A[i]这三者里面取一即可。有了这个只关乎最终状态,不关乎过程细节的结论,解题过程可以大大简化。 这里用了O(N)空间,所以内存开销比第一种解法大。 解法3——优化的DP解法 思考以上DP解法的空间开销过大的原因,是因为保存了整个DP表。其实整个过程中,获得dp[i]的值只需要dp[i-1]的值,所以是不需要保存整个DP表的。 这样一来,DP可以用滚动数组进行优化。简单的写法其实就是设一对prevMin/prevMax表示上一个值,以及还有一对curMin/curMax表示当前值。 解法4——分治法 如果数组里面没有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之间的小数。 |
|
来自: 雪柳花明 > 《LeetCode》