We can find the solution for each prefix
nums[:i], by knowing three things about the previous prefix
nums[:i - 1]:
- the max product.
- the largest product which includes the last number in the prefix.
- 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 for num in nums[1:]: small, _, large = sorted([x * num for x in 1, small, large]) best = max(best, large) return best