leetcode-152-Maximum Product Subarray

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

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

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.

問(wèn)題本質(zhì)：

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

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

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)