Python 5 clear lines with DP explanation


  • 1
    J

    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
    

Log in to reply
 

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