Python easy DP solution

  • 0

    Instead of having a single dp table, we create two: one to keep track of max and min product ending at index i. This will get around the issue of a very negative element times another negative which produces a big positive value.

    def maxProduct(self, nums):
        dp_max, dp_min = [0] * len(nums), [0] * len(nums)
        dp_max[0] = dp_min[0] = nums[0]
        for i in range(1, len(nums)):
            dp_max[i] = max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
            dp_min[i] = min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
        return max(dp_max)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.