Q152 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.
解题思路:

先来回顾最大子段和问题:Q53 Maximum Subarray

最大字段积不同于最大子段和的一点就是,可能前面累积的是最小乘积,结果遇到了一个负值,就变成了最大乘积。因此,我们需要记录前 k-1 个数的局部最大值和局部最小值,然后遇到第 k 个数时,分别相乘,更新局部最大值和局部最小值。同时,还要有一个全局最大值,来记录最大乘积。

这是一个动态规划问题,时间复杂度:O(n),空间复杂度:O(1)

举例:nums = [2,-2,3,2,-2,0,-2],此时列表已经遍历了 [2,-2,3,2],并且记录了 localMax = 6 和 localMin = -24,当遇到下一个数 -2 时,分别与localMax 和 localMin 相乘,得到 -12 和 24,此时应该将 localMax 更新为24,即取 -12, 24 以及当前数 -2 中的较大一个(为什么还要和当前数比?因为比如遍历到 [2,-2],结果遇到了 3,此时 localMax 应该更新为 3); localMin 更新为 -12,即取 -12, 24 以及当前数 -2 中的较小一个。同时,将 globalMax 更新为 24。因此,我们只需要遍历一遍列表就可以找到最大子段积。

注意点:

当遇到 0 后, localMax 和 localMin 均会被更新为 0,但是 gloabalMax 还是 48,这也就是说,localMax 和 localMin 只是记录了局部一段的最大值和最小值,而真正的最大值由 gloabalMax 来记录。

Python实现:
class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        globalMax = localMax = localMin = nums[0]
        for i in range(1, len(nums)):
            cur1 = localMax * nums[i]
            cur2 = localMin * nums[i]
            localMax = max(cur1, cur2, nums[i])  # 更新局部最大值
            localMin = min(cur1, cur2, nums[i])  # 更新局部最小值
            globalMax = max(globalMax, localMax) # 更新全局最大值
        return globalMax

a = [2,-2,3,2,-2,0,-2]
print(Solution().maxProduct(a)) # 48 # [2,-2,3,2,-2]

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

动态规划--Kin

30140
来自专栏余林丰

8.动态规划(1)——字符串的编辑距离

  动态规划的算法题往往都是各大公司笔试题的常客。在不少算法类的微信公众号中,关于“动态规划”的文章屡见不鲜,都在试图用最浅显易懂的文字来描述讲解动态规划,甚至...

751100
来自专栏desperate633

LeetCode 149. Max Points on a Line分析代码

将x,y的差值求最大公约数,约到最简洁的形式,然后存入map中,对每个点这样操作,如果最后x,y最后相等,那么就说明两个点具有相同的斜率,在一条直线上。同时不要...

10930
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

602140
来自专栏机器学习从入门到成神

机器学习中数据处理与可视化的python、numpy等常用函数

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

13510
来自专栏calmound

zoj 1315 Excuses, Excuses!

题意:简单题,读懂题目就很好写了,这里要说的是,题目并没有叙述每句话里的单词长度是多少,所以导致我的数组开小了,一直SF,后来把数组开大后就A了        ...

35550
来自专栏人工智能LeadAI

Tensorflow教程: tf.Variable() 和tf.get_variable()

1、使用tf.Variable时,如果检测到命名冲突,系统会自己处理。使用tf.get_variable()时,系统不会处理冲突,而会报错

14130
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

23330
来自专栏desperate633

LintCode 旋转字符串题目分析代码

样例 对于字符串 "abcdefg". offset=0 => "abcdefg" offset=1 => "gabcdef" offset=2 => ...

13920
来自专栏数据结构与算法

25:最长最短单词

25:最长最短单词 总时间限制: 1000ms 内存限制: 65536kB描述 输入1行句子(不多于200个单词,每个单词长度不超过100),只包含字母、空格...

398100

扫码关注云+社区

领取腾讯云代金券