DP-LeetCode152. 乘积最大子数组（Python）

1、题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

2、代码详解

法一：可扩展性好（推荐）

二维数组，2*2大小，一维存最大值，一维存负最大值

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]        :rtype: int
        """
        if nums is None:
            return 0
        dp = [[0 for _ in range(2)] for _ in range(2)]  # 只需保存前一次的结果，所以只需要2*2数组
        # 保存最大值dp[][0]，负最大值（即最小值）dp[x][1]        dp[0][1], dp[0][0], res = nums[0], nums[0], nums[0]        for i in range(1, len(nums)):
            x, y = i % 2, (i-1) % 2  # 滚动数组，交替保存
            dp[x][0] = max(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])  # 存最大值
            dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])  # 存最小值
            res = max(res, dp[x][0])
        return res

法二：可读性好，通用性差（只适用于本题）

class Solution(object):
    def maxProduct(self, nums):
        if nums is None:
            return 0
        res, curMax, curMin = nums[0], nums[0], nums[0]        for i in range(1, len(nums)):
            num = nums[i]            curMax, curMin = curMax * num, curMin * num
            curMax, curMin = max(curMax, curMin, num), min(curMax, curMin, num)
            res = max(curMax, res)
        return res

https://time.geekbang.org/course/detail/130-69781

作者：NLP_victor