详解连续子数组的最大累乘之动态规划解法

1

此题出自LeetCode：152. Maximum Product Subarray，大意求子数组的最大值，举例子1：

1Input: [2,3,-2,4]
2Output: 6
3
4Explanation: [2,3] has the largest product 6.

例子2：

1Input: [-2,0,-1]
2Output: 0
3Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

这个题目，当然可以用穷举所有子数组的方法，找出最大值，时间复杂度妥妥地为O(n^2)，这显然不是我们想要的。如何用DP降低到O(n)才是我们的目标，这才是算法的魅力所在，接下来，总结DP求解的思维过程。

2

分析一个数组，假定每一个元素都不小于0，如，[2, 3, 0 , 4], ok, 当子数组 [2]，最大连乘为2，当子数组为[2,3]，最大连乘可能的组合：3，2*3，最大子数组为：[2,3]，如果标记dp[i] 表示为以i(含i)为索引的数组的最大值，则 dp[i] 如何 从 dp[i-1] 中推导出来？

dp[i] 取值有以下几种情况：

1) a[i]

2) dp[i-1] * a[i]

则，dp[i] = max( a[i], dp[i-1] * a[i] )

验证以上数组当索引为2时，dp[2] = max(0, 6*0) = 0，dp[3] = max(4, 0 *4) = 4, 因此 max(dp[0],dp[1],dp[2],dp[3]) = dp[1]

如果这道题目

如果元素都为非负，以上递推公式就可解决此题。但是这道题目难就难在元素有负值，比如：[-2, -3, -2, 4]，如果还是按照上述递推公式，dp[0] = -2, dp[1] = 6, dp[2] = -2 , dp[3] = 4，因此最大累乘为：6， 这是错误的。最大累乘应该为：(-3)*(-2)*4 = 24.

问题出在哪里？ dp[0], dp[1] 计算正确，dp[2]错误，因为[-2,-3,-2] 的最大累乘为：(-3)*(-2) = 6.

在哪里摔倒就在哪里爬起来，在计算dp[2]时，按照递推 max(a[2], a[2]*dp[1])计算时，a[2]*dp[1] = -12 ，如果我们再标记一个最小值，dpmin[i]表示为以i为索引的最小值，dpmin[0] = -2, 因为a[1] = -3 <0, 求 dpmin[1] 时先和dp[0]和dpmin[0]交换，因此，dpmin[1] = min(-3, -3*dpmin[0] ) = -3，同样，求dpmin[2]时，dp[1]和dpmin[1]交换，dpmin[2] = min(-2, -2*dp[1] ) = -12, dp[2] = max(-2, -2*dpmin[1]) = 6.

以上关键步骤，涉及到对第 i 个元素为负数时的处理过程，dp[i] 和 dpmin[i] 计算有怎样的依赖关系，当a[i] 为负数时，dp[i-1] * a[i] 变为最小，dpmin[i-1] * a[i] 变为最大，因此交换dp[i-1]和dpmin[i-1]后，dp[i] = max(a[i], dpmin[i-1]*a[i]), dpmin[i] = min(a[i], dp[i-1]*a[i]).

分析完毕

3

本题的代码如下：

 1class Solution(object):
 2    def maxProduct(self, nums):
 3        """
 4        :type nums: List[int]
 5        :rtype: int
 6        """
 7        def swap(a, b):
 8            tmp = a
 9            a = b
10            b = tmp
11            return a, b
12        min_prod, max_prod =nums[0], nums[0]
13        ret = nums[0]
14        for it in nums[1:]:
15            if it < 0:min_prod,max_prod = swap(min_prod,max_prod)
16            max_prod = max(it, it * max_prod)
17            min_prod = min(it, it * min_prod)            
18            ret = max(max_prod, ret)
19        return ret

求连续子数组的最小值代码稍作修改也出来了。本题还有其他优秀的解吗？欢迎大家分享。

如果是求子数组的非连续最大、小值，该怎么求解大家思考一下吧。