# Python 5 clear lines with DP explanation

• We can find the solution for each prefix `nums[:i]`, by knowing three things about the previous prefix `nums[:i - 1]`:

1. the max product.
2. the largest product which includes the last number in the prefix.
3. the smallest product which includes the last number in the prefix.

We need to keep track of the smallest product ending here because if the next number is negative, multiplying it by another negative number might result in the best solution.

Here is the recurrence relationship for each prefix `nums[:i] for i in 1...len(nums)` where `num` is the new number:

``````small_ending_here[i] = min(num * small_ending_here[i - 1],
num * large_ending_here[i - 1], num)

large_ending_here[i] = max(num * small_ending_here[i - 1],
num * large_ending_here[i - 1], num)

best[i] = max(large_ending_here[i], best[i - 1])
``````

Because each solution only refers to the previous solution, we don't need to keep track of all values for smallest, largest, and best. Here is the code:

``````def maxProduct(nums):
small = large = best = nums[0]
for num in nums[1:]:
small, _, large = sorted([x * num for x in 1, small, large])
best = max(best, large)
return best
``````

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