Simple Python DP Solution with O(n) complexity


  • 0
    H

    """
    class Solution(object):
    def maxProduct(self, nums):
    result = nums[0]
    max_pos = nums[0] if nums[0] > 0 else 0
    min_neg = nums[0] if nums[0] < 0 else 0
    for ind, num in enumerate(nums[1:]):
    if num > 0:
    max_pos = max(num, max_pos*num)
    min_neg *= num
    elif num == 0:
    max_pos = 0
    min_neg = 0
    else:
    max_pos_tmp = min_neg * num
    min_neg = min(max_pos * num, num)
    max_pos = max_pos_tmp

            if result < max_pos:
                result = max_pos
        return result
    

    """


Log in to reply
 

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