Minimal python DP solution (no fancy code optimizing)

  • 0

    This is a minimal DP solution written in Python. I want to keep it this way to make it easier for people who want to practice formalizing the DP solution.

    The first step in design a DP solution is to define the sub-optimal problem. Notice that in this case, the sub-array has to be contiguous, so it is important that the sub-optimal problem has to end at index i in order to combine with i+1.

    Let's define max_p[i] to be the largest product of the sub-array ends at index i.

    Secondly, we try to break the calculation at index i to cases of the sub-optimal solution at index i-1 by stating our observations: the largest product of sub-array ends at index i is either

    • nums[i] multiply the previous largest value if nums[i] is positive
    • nums[i] multiply the previous smallest value if nums[i] is negative since we might have a flipped sign, taking the previous smallest value guarantee that we will multiply our negative nums[i] with a negative value if such flipped sign happens
    • nums[i]

    Give me the code:

    class Solution:
        def maxProduct(self, nums):
            :type nums: List[int]
            :rtype: int
            max_p = [0] * len(nums)
            min_p = [0] * len(nums)
            max_p[0] = min_p[0] = nums[0]
            for i in range(1, len(nums)):
                max_p[i] = max(nums[i], nums[i] * max_p[i-1], nums[i] * min_p[i-1])
                min_p[i] = min(nums[i], nums[i] * max_p[i-1], nums[i] * min_p[i-1])
            return max(max_p)

Log in to reply

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