Beyond awesome | 越而胜己

Link to problem:

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)
                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]
                dpMax += nums[i]
            globalMax = max(globalMax, dpMax)
        return globalMax
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.