Maximum Product Subarray http://www.geeksforgeeks.org/maximum-product-subarray/

maxprodSubArray.py

# Source : http://www.geeksforgeeks.org/maximum-product-subarray/

def maxProd(input):
    prod = temp_prod = 1
    i=0
    negativeCount = 1
    start_SubArray = -1
    end_SubArray = -1
    while i < len(input) :
        if input[i] == 0 or i == len(input)-1: #end condition 1 and 2
            if input[i] == 0:   #end condition 1
                if start_SubArray == -1:   #0 at the start
                    i = i + 1
                    start_SubArray = i
                    
                    end_SubArray = -1 #resetting
                    continue
                else:                    #0 somewhere else
                    prod = findTempProdforSub( input, start_SubArray, end_SubArray, temp_prod, prod, negativeCount )
            else: #end condition 2
                end_SubArray = i    #end of the array
                temp_prod *= input[i]
                if input[i] < 0:
                    negativeCount *= -1
                prod = findTempProdforSub( input, start_SubArray, end_SubArray, temp_prod, prod, negativeCount )

            negativeCount = 1 #resetting        
            temp_prod = 1 #resetting
        
        else: #normal cases
            if start_SubArray == -1:
                start_SubArray = i
            end_SubArray = i    #end of the array
            temp_prod *= input[i]
            if input[i] < 0:
                negativeCount *= -1
            
            
        i = i + 1
    #end of while
        
    return prod
    
    
    
def findTempProdforSub(input, start_SubArray, end_SubArray, temp_prod, prod, negativeCount  ):
    
    if input[start_SubArray] > 0 :  #started with positive
        if negativeCount == 1 :  #even negatives
            prod = max( prod, temp_prod )
        else: # odd negatives
            prod = max( prod, temp_prod/ input[end_SubArray] )
    else: #started with negative
        if negativeCount == 1 :  #even negatives
            prod = max( prod, temp_prod )
        else: # odd negatives
            temp_prod_1 = temp_prod / input[start_SubArray] #skip first
            temp_prod_2 = temp_prod / input[end_SubArray] #skip last
            temp_prod = max( temp_prod_1, temp_prod_2 )
            prod = max(prod, temp_prod)
            
    return prod



input = [6, -3, -10, 0, 2]
input2 = [-1, -3, -10, 0, 60]
input3 = [-2, -3, 0, -2, -40]

print maxProd( input3 )