# Minimal python DP solution (no fancy code optimizing)

• 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)
``````

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