This DP Python Memory limit excessed


  • 0
    W
    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n=len(nums)
            re=[[([],0) for i in range(n)] for j in range(n)] 
            for i in range(n):
                re[i][i]=([nums[i]],1)
            max_len=1
            for k in range(1,n):
                for i in range(n-k):
                    j=i+k
                    l,t=re[i][j-1]
                    max_len=max(max_len,t)
                    if nums[j]>l[-1]:
                        re[i][j]=(l+[nums[j]],t+1)
                        max_len=max(max_len,t+1)
                    else:
                        re[i][j]=re[i][j-1]
            return max_len

  • 0
    W
    class Solution(object):
        def lengthOfLIS(self, nums):
            n=len(nums)
            re=[[(0,0) for i in range(n)] for j in range(n)] 
            for i in range(n):
                re[i][i]=(nums[i],1)
            max_len=1
            for k in range(1,n):
                for i in range(n-k):
                    j=i+k
                    l,t=re[i][j-1]
                    max_len=max(max_len,t)
                    if nums[j]>l:
                        re[i][j]=(nums[j],t+1)
                        max_len=max(max_len,t+1)
                    else:
                        re[i][j]=re[i][j-1]
            return max_len
    

    Update the DP, it is Time Limit Out


Log in to reply
 

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