Python DP, TLE, three steps.


  • 0
    W

    First, create largest k sequence from one array.
    Second, merge two arrays to get the largest sequence.
    Finally, loop with different length from two arrays and compare to get the largest sequence.

    class Solution:
        # @param {int[]} nums1 an integer array of length m with digits 0-9
        # @param {int[]} nums2 an integer array of length n with digits 0-9
        # @param {int} k an integer and k <= m + n
        # @return {int[]} an integer array
        def maxNumber(self, nums1, nums2, k):
            n=len(nums1)
            m=len(nums2)
            max_n=[0 for i in range(k)]
            for i in range(k+1):
                if i<=n and k-i<=m:
                    s=self.merge(self.maxN(nums1,i),self.maxN(nums2,k-i))
                    max_n=max(max_n,s)
            return max_n
    
        def maxN(self,nums,k):
            n=len(nums)
            if n==k:
                return nums
            elif k==0 or n<k:
                return []
            i=nums.index(max(nums))
            if n-i==k:
                return nums[i:]
            elif n-i>k:
                return [nums[i]]+self.maxN(nums[i+1:],k-1)
            elif n-i<k:
                return self.maxN(nums[:i],k+i-n)+nums[i:]
    
        def merge(self,nums1, nums2):
            nums=[]
            n=len(nums1)
            m=len(nums2)
            if n==0:
                return nums2
            if m==0:
                return nums1
            arr=[[]]
            for i in range(n):
                arr.append(nums1[:i+1])
            for i in range(1,m+1):
                arr[0]=nums2[:i]
                for j in range(1,n+1):
                    arr[j]=max(arr[j-1]+[nums1[j-1]],arr[j]+[nums2[i-1]])
            return arr[n]

Log in to reply
 

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