leetcode-152-Maximum Product Subarray

thursday 发布于2019-07-30 17:32 / 2802人阅读

摘要：问题本质本质动态规划问题。局部最优，全局最优。乘法问题，存在的情况是负数或者正数，或者从当前数开始新的连续元素相乘可能发生的情况在某个节点，继续之前的增大减小，从此节点转折。所以只要在局部动态中，保持最大最小当前，进行判断保留即可。

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

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

Example 2:

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

问题本质：

本质：动态规划问题。 局部最优，全局最优。
 product-乘法问题，存在的情况是 负数或者正数，或者从当前数开始新的连续元素相乘
 可能发生的情况： 在某个节点，继续之前的增大/减小，从此节点转折。
 所以只要在局部动态中，保持最大/最小/当前，进行判断保留即可。

应用：挖掘问题的本质，将问题抽象化，  局部：之前的值和当前值是同乡还是异向的问题，同向则被覆盖，异向则被保留。如此迭代。

class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        final_max=max_num=min_num=nums[0]
        for num_cur in nums[1:]:
            # min_num=min(num_cur*min_num,num_cur)
            max_num_tmp=max(num_cur*min_num,num_cur*max_num)
            min_num=min(num_cur*min_num,num_cur*max_num,num_cur)
            max_num=max(max_num_tmp,num_cur)
            final_max=max(max_num,final_max)
        return final_max
if __name__=="__main__":
    st=Solution()
    num=[2,3,-2,-5,4,-5,8]
    # num=[-2,0,-1]
    # num=[2,3,-2,4]
    num=[-1,-2,-9,-6]
    out=st.maxProduct(num)
    print(out)

云服务器服务器托管 subarray Product 阿里大鱼product 阿里大于product

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42256.html

Leetcode[152] Maximum Product Subarray

摘要：复杂度思路要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...

_ipo 2019-08-14 16:49 评论0 收藏0
leetcode152 Maximum Product Subarray

摘要：题目要求从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较，是因为如果是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。题目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 评论0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

摘要：这是一道简单的动规题目，同步更新数组解决了为负数的问题。即使是求最小乘积子序列，也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

meteor199 2019-08-14 15:21 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0