O(n^2) solution to maximum product subaray results in 'time limit exceeded' dillema in lee-CodePudding

I was attempting to solve the maximum product subarray leetcode problem (https://leetcode.com/problems/maximum-product-subarray/) in python but only 186/188 test cases passed, the remaining two producing the time limit exceeded error, inspite of the solution being O(n^2). What am I doing wrong ?

class Solution:
def max_element(self,a,b):
        if(a>b):
                return(a)
        else:
                return(b)
def compute_product(self,products,i,j,array):
        if(i==j):
            products[i][j]=array[i]
            return(array[i])
        if(products[i][j]!=-1):
            return(products[i][j])
        products[i][j]=self.compute_product(products,i,j-1,array)*array[j]
        self.compute_product(products,i 1,j,array)
        return(products[i][j])
def max_product_subarray(self,table,products,i,j,array):
        if(i==j):
            table[i][j]=array[i]
            return(array[i])
        if(table[i][j]!=(-1)):
            return(table[i][j])
        result=-99999
        case1=0
        if(products[i][j]!=-1):
            case1=products[i][j]
        else:
            case1=self.compute_product(products,i,j,array)
        case2=self.max_product_subarray(table,products,i,j-1,array)
        case3=self.max_product_subarray(table,products,i 1,j,array)
        result=self.max_element(case1,self.max_element(case2,case3))
        table[i][j]=result
        return(result)
def compute_max_product_subarray(self,array):
    table=[[(-1) for j in range(len(array))]for i in range(len(array))]
    products=[[(-1) for j in range(len(array))]for i in range(len(array))]
    return(self.max_product_subarray(table,products,0,len(array)-1,array))
def maxProduct(self, nums: List[int]) -> int:
    return(self.compute_max_product_subarray(nums))

CodePudding user response：

If the values are a mix of positives and negatives and/or zeros, the answer includes only the largest candidate windows with an even count of negatives and no zeros, and the zero candidate. Count the number of negatives between each zero or end of list. For each count, if the count is even, the candidate is the product of all the elements in that section. If the count is odd, check two candidates; one from the earliest positive before the second negative element to the end of the section, and the other from the beginning of the section to the last positive passed the second to last negative element. The 0 candidate might be relevant in case no positive candidates can be formed.

CodePudding user response：

The problem of maximum-sum-subarray can be solved in O(n) time complexity. With maximum product-subarray, the algorithm can be made faster by partitioning the array around the zero values and scanning within these partitions. Any crossover across these partitions are always zero, so that does not need any computation.