O(m*n*k) DP solution, TLE
Now I find there are O(max(m, n) * k) greedy solution from the posts. My first idea is DP. Let f(i,j,k) represent maximum number of length k generated from nums
Now I find there are O(max(m, n) * k) greedy solution from the posts. My first idea is DP. Let f(i,j,k) represent maximum number of length k generated from nums1[1:i] and nums2[1:j]. the formula is: f(i,j,k) = max{f(i-1,j,k), f(i,j-1,k), f(i-1,j,k-1) + [nums1[i]], f(i,j-1,k-1) + [nums2[j]] } The implementation is as follows,\n\n        def maxNumber(self, nums1, nums2, k):\n        """\n        :type nums1: List[int]\n        :type nums2: List[int]\n        :type k: int\n        :rtype: List[int]\n        """\n        m = len(nums1)\n        n = len(nums2)\n        if k > m + n or k <= 0:\n            return []\n        #kk = 0\n        pre_dp = [[[] for _ in xrange(n + 1)] for __ in xrange(m + 1)]\n        \n        for kk in xrange(1, k + 1):\n            #kk\n            dp = [[[] for _ in xrange(n + 1)] for __ in xrange(m + 1)]\n            #i >= kk, j = 0\n            for i in xrange(kk, m + 1):\n                dp[i][0] = max(pre_dp[i-1][0] + [nums1[i-1]], dp[i-1][0])\n                \n            #i = 0, j >= kk\n            for j in xrange(kk, n + 1):\n                dp[0][j] = max(pre_dp[0][j-1] + [nums2[j-1]], dp[0][j-1])\n            \n            #i > 0, j > 0\n            for i in xrange(1, m + 1):\n                for j in xrange(1, n + 1):\n                    if i + j < kk:\n                        continue\n                    dp[i][j] = max(dp[i-1][j], \\\n                                    dp[i][j-1], \\\n                                    pre_dp[i-1][j] + [nums1[i-1]], \\\n                                    pre_dp[i][j-1] + [nums2[j-1]])\n            pre_dp, dp = dp, pre_dp\n        return pre_dp[m][n]
[]