My python code get TLE . Can someone help me ?


  • 0
    R

    Algorithm :

    Assume f[i][j] to be the maximum product subarray of nums[i:j+1]

    therefore
    for f[0][1] f[1][2] ...
    f[i][j] = max(f[i+1][j],f[i][j-1],nums[i]*nums[j])

    for other f[i][j]
    f[i][j] = max(f[i+1][j],f[i+1][j-1],f[i][j-1],sum)
    where sum is nums[i]*nums[i+1]*nums[i+2]*...*nums[j]

    so following is my code

    class Solution(object):
        def maxProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            # 2d array
            f = [([0] * len(nums)) for i in range(len(nums))]
            # init
            for i in xrange(len(nums)):
                f[i][i] = nums[i]
            for window in xrange(1,len(nums)+1):
                for i in xrange(len(nums)-window):
                    j = i + window
                    if j-1 >= i+1:
                        # e.g f[0][3]
                        # core algorithm
                        sum = 1
                        for x in xrange(i,j+1):
                            sum *= nums[x]
                        f[i][j] = max(f[i+1][j],f[i+1][j-1],f[i][j-1],sum)
                    else:
                        # e.g f[0][1]
                        f[i][j] = max(f[i+1][j],f[i][j-1],nums[i]*nums[j])
            return f[0][len(nums)-1]
    

    But my solution get TLE
    How to optimize it ?
    Thanks


Log in to reply
 

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