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
Give me the code:
class Solution: def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ max_p =  * len(nums) min_p =  * len(nums) max_p = min_p = nums 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)