leetcode-152-Maximum Product Subarray

thursday 發(fā)布于2019-07-30 17:32 / 2910人閱讀

摘要：問題本質本質動態(tài)規(guī)劃問題。局部最優(yōu)，全局最優(yōu)。乘法問題，存在的情況是負數(shù)或者正數(shù)，或者從當前數(shù)開始新的連續(xù)元素相乘可能發(fā)生的情況在某個節(jié)點，繼續(xù)之前的增大減小，從此節(jié)點轉折。所以只要在局部動態(tài)中，保持最大最小當前，進行判斷保留即可。

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.

問題本質：

本質：動態(tài)規(guī)劃問題。 局部最優(yōu)，全局最優(yōu)。
 product-乘法問題，存在的情況是 負數(shù)或者正數(shù)，或者從當前數(shù)開始新的連續(xù)元素相乘
 可能發(fā)生的情況： 在某個節(jié)點，繼續(xù)之前的增大/減小，從此節(jié)點轉折。
 所以只要在局部動態(tài)中，保持最大/最小/當前，進行判斷保留即可。

應用：挖掘問題的本質，將問題抽象化，  局部：之前的值和當前值是同鄉(xiāng)還是異向的問題，同向則被覆蓋，異向則被保留。如此迭代。

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)

云服務器 GPU云服務器 subarray Product 阿里大魚product 阿里大于product

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/42256.html

Leetcode[152] Maximum Product Subarray

摘要：復雜度思路要保留一個到某一位來看的最大值和最小值。因為在數(shù)組中有負數(shù)的出現(xiàn)，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個數(shù)相乘得到，也可能是最小值和這個數(shù)相乘得到的。 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

摘要：題目要求從一個整數(shù)數(shù)組中找到一個子數(shù)組，該子數(shù)組中的所有元素的乘積最大。比如數(shù)組的最大乘積子數(shù)組為思路與代碼這題目考察了動態(tài)編程的思想。至于為什么還要比較，是因為如果是一個負數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。題目要求 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

摘要：這是一道簡單的動規(guī)題目，同步更新數(shù)組解決了為負數(shù)的問題。即使是求最小乘積子序列，也可以通過取和的最小值獲得。 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 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫現(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫～現(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0