搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > Python与算法社区 > 详解连续子数组的最大累乘之动态规划解法

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

Python与算法社区 2018-06-28


动态规划技术(DP),能获得更好的时间性能。不过,灵活运用还需要多加训练,多多思考。


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


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

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


更多好文:


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《详解连续子数组的最大累乘之动态规划解法》的版权归原作者「Python与机器学习算法频道」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注Python与机器学习算法频道微信公众号

Python与机器学习算法频道微信公众号:alg-channel

Python与机器学习算法频道

手机扫描上方二维码即可关注Python与机器学习算法频道微信公众号

Python与机器学习算法频道最新文章

精品公众号随机推荐