Long, but beats 97% of submissions


  • 0
    E

    The main idea is that we must consider 3 factors:

    • how many negative numbers there are (if they are even we do not care)
    • how many zeros (in this case it is enough to split the array in subarrays and call recursively on each one in order to see which has the greatest product)
    • where are the negative numbers
    class Solution(object):
        def maxProduct(self, nums):
        	ind=[]
        	zero=[]
        	zeroadd=[]
        	numb=0
        	numb2=0
        	le=len(nums)
        	if le==1:
        		return nums[0]
        	inn=-1
        	for x in nums:
        		inn+=1
        		if x<0:
        			numb+=1
        			ind.append(inn)
        			zeroadd.append(x)
        		elif x>0:
        			zeroadd.append(x)
        		else:
        			numb2+=1
        			zero.append(zeroadd)
        			zero.append([0])
        			zeroadd=[]
        	zero.append(zeroadd)
        	if numb2>0:
        		prods=[]
        		for y in zero:
        			if len(y)>0:
        				prods.append(self.maxProduct(y))
        		return max(prods)
    
        	if numb==0 or numb%2==0:
        		return reduce((lambda x,y:x*y),nums)
        		return nums
        	elif numb==1 and ind[0]==0:
        		return reduce((lambda x,y:x*y),nums[1:le])
        	elif numb==1 and ind[0]==le-1:
        		return reduce((lambda x,y:x*y),nums[0:le-1])
        	elif numb==1 and ind[0]!=0:
        		caso1=reduce((lambda x,y:x*y),nums[0:ind[0]])
        		caso2=reduce((lambda x,y:x*y),nums[ind[0]+1:le])
        		return max(caso1,caso2)
        	else:
        		caso1=reduce((lambda x,y:x*y),nums[0:ind[-1]])
        		caso2=reduce((lambda x,y:x*y),nums[ind[0]+1:le])
        		return max(caso1,caso2)
    

Log in to reply
 

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