My very urgly o(n) python solution


  • 0
    H
    class Solution(object):
        def maxProduct(self, nums):
            nums1=[]
            t=-1
            if len(nums)==1:
                return nums[0]
            for i in range(len(nums)):
                if nums[i]<0:
                    if t>=0:
                        nums1.append(t)
                        t=-1
                    nums1.append(nums[i])
                elif nums[i]==0:
                    if t>0:
                        nums1.append(t)
                    t=0
                else:
                    if t==0:
                        nums1.append(t)
                        t=nums[i]
                    elif t==-1:
                        t=nums[i]
                    else:
                        t=t*nums[i]
            if t!=-1:
                nums1.append(t)
            dp1=[]
            dp2=[]
            nums2=[]
            n=len(nums1)
            for i in range(len(nums1)):
                nums2.append(nums1[n-1-i])
                if nums1[i]>0:
                    dp1.append(nums1[i])
                    dp2.append(nums2[i])
                else:
                    dp1.append(0)
                    dp2.append(0)
            max1=self.getmax(nums1,dp1)
            max2=self.getmax(nums2,dp2)
            if max1>max2:
                return max1
            else:
                return max2
        def getmax(self,nums,dp):
            t=0
            n=len(nums)
            s=0
            for i in range(len(nums)):
                if nums[i]<0:
                    if i==0 or dp[i-1]==0:
                        t=nums[i]
                    else:
                        t=nums[i]*dp[i-1]
                    if i+1<=n-1:
                        if nums[i+1]<0:
                            i+=1
                            dp[i]=t*nums[i]
                            s=1
                        elif nums[i+1]==0:
                            i+=1
                            s=1
                    if i+2<=n-1:
                        if nums[i+2]<0 and s!=1:
                            i+=2
                            dp[i]=t*nums[i]*nums[i-1]
                        elif nums[i+2]==0 and s!=1:
                            i+=2
                    s=0
                elif nums[i]>0:
                    if i!=0 and dp[i-1]>0:
                        dp[i]=dp[i-1]*nums[i]
            return max(dp)
    

Log in to reply
 

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