python use no sort, but slow


  • 2
    D

    Time O(n), Space O(1) ?

    class Solution(object):
        def maximumProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            hi = max(nums[0],nums[1])
            lo = min(nums[0],nums[1])
            
            hiprod2 = nums[0]*nums[1]
            loprod2 = nums[0]*nums[1]
            
            hiprod3 = nums[0]*nums[1]*nums[2]
            
            for num in nums[2:]:
                hiprod3 = max(hiprod3, hiprod2 * num, loprod2 * num)
                
                hiprod2 = max(hiprod2, hi * num, lo * num)
                loprod2 = min(loprod2, hi * num, lo * num)
                
                hi = max(num, hi)
                lo = min(num, lo)
                
            return hiprod3
    

  • 0

    @drfluid said in python use no sort, but slow:

    Space O(1) ?

    No, but just because of nums[2:].


Log in to reply
 

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