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

动态规划技术(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与机器学习算法频道(alg-channel)

原文发表时间:2018-06-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

1011
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3434
来自专栏DHUtoBUAA

快速排序算法思路分析和C++源代码(递归和非递归)

  快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试...

4077
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

3617
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

3727
来自专栏java初学

top K 问题

48216
来自专栏aCloudDeveloper

LeetCode:5_Longest Palindromic Substring | 最长的回文子串 | Medium

题目: Given a string S, find the longest palindromic substring in S. You may assum...

22810
来自专栏desperate633

[编程题] 制造回文分析代码

我们知道回文串的话,就是前后相等,那么一个字符至少出现两次,除了一种情况,就是可以有一个字符只出现一次,就是这个字符在中间。 所以,我们的思路就是统计出现奇数...

872
来自专栏窗户

有限域(3)——多项式环的商环构造有限域

  接着上两章内容,我们还是得继续寻找有限域的构造方法。上章证明矩阵环是个单环,自然是没戏了,但我们还可以考虑多项式环。

3232
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1212

扫码关注云+社区

领取腾讯云代金券