DP-less code


  • 0
    X
    def prod(nums):
        return reduce(lambda a,b:a*b, nums) if nums else 1
    
    def splitBy(lst, delimeter):
        idxs = [i for (i,x) in enumerate(lst) if x == delimeter]
        begins = [0] + [i+1 for i in idxs]
        ends = idxs + [len(lst)]
        return [lst[begin:end] for (begin, end) in zip(begins, ends)]
    
    class Solution(object):
        def maxProduct(self, nums):
            splits = splitBy(nums, 0)
            results = [self.maxProduct_nozero(lst) for lst in splits if lst]
            if not results: #has 0 only
                return 0
            split_max = max(results)
            if len(splits) > 1: #has 0
                return max(split_max, 0)
            else:
                return split_max
            
        def maxProduct_nozero(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 1:
                return nums[0]
            neg_ids = filter(lambda i:nums[i] < 0, range(len(nums)))
            if len(neg_ids) % 2 == 0:
                return prod(nums)
            left = neg_ids[0]
            right = neg_ids[-1]
            if prod(nums[:left+1]) < prod(nums[right:]):
                #include left, exclude right
                return prod(nums[:right])
            else:
                return prod(nums[left+1:])
    

    for an array arr without 0:
    if arr contains even amount of negatives, return prod(arr)
    else either abandon beginning numbers until the first negative, or abandon since the last nagative.

    for an array arr with 0:
    split by 0, find max-prod for every subarray. compare the result with 0 if the original contains 0.

    48 ms


Log in to reply
 

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