越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/maximum-product-subarray/

This problem is an extension of LC53. Maximum Subarray, by replacing addition with multiplication. The tricky part about multiplication is that multiplying by a negative number flips the maximum and the minimum. Therefore, when we do dynamic programming, we want to keep both the maximum and the minimum as our states.

Let dpmax[i] and dpmin[i] be the maximum/minimum product subarray that ends with nums[i]. When nums[i] >= 0, we can easily find recurrences dpmax[i] = max(nums[i], dpmax[i-1] * nums[i]) and dpmin[i] = min(nums[i], dpmin[i-1] * nums[i]); when nums[i] < 0, dpmax[i] = max(nums[i], dpmin[i-1] * nums[i]) and dpmin[i] = min(nums[i], dpmax[i-1] * nums[i]).

Thus the answer is just the maximum of all dpmax[i]s.

此题是 LC53. Maximum Subarray 的加强版,只是把加法换成了乘法。乘法的麻烦之处在于乘一个负数会使最大变为最小,最小变为最大。因此,我们动态规划时需要同时保存最大和最小两个状态。

dpmax[i]dpmin[i] 分别表示以 nums[i] 为最后一个元素的子数组的最大和最小乘积。当 nums[i] >= 0 时,不难找到状态转移方程 dpmax[i] = max(nums[i], dpmax[i-1] * nums[i])dpmin[i] = min(nums[i], dpmin[i-1] * nums[i]);而 nums[i] < 0 时,dpmax[i] = max(nums[i], dpmin[i-1] * nums[i])dpmin[i] = min(nums[i], dpmax[i-1] * nums[i]).

由此,答案即是所有 dpmax[i] 的最大值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        globalMax = nums[0]
        dpMax, dpMin = nums[0], nums[0]
        for i in range(1, len(nums)):
            dpMaxPrev, dpMinPrev = dpMax, dpMin
            if nums[i] >= 0:
                dpMax = max(nums[i], nums[i] * dpMaxPrev)
                dpMin = min(nums[i], nums[i] * dpMinPrev)
            else:
                dpMax = max(nums[i], nums[i] * dpMinPrev)
                dpMin = min(nums[i], nums[i] * dpMaxPrev)
            globalMax = max(globalMax, dpMax)
        return globalMax

The solution to LC53. Maximum Subarray is also attached below for comparison.

这里也放上 LC53. Maximum Subarray 的解答以供对比。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dpMax = nums[0]
        globalMax = nums[0]
        for i in range(1, len(nums)):
            if dpMax < 0:
                dpMax = nums[i]
            else:
                dpMax += nums[i]
            globalMax = max(globalMax, dpMax)
        return globalMax