Easy to understand greedy C++ solution O(NMK)
We pick optimal digit one by one. At each phase, let dp[sa] be the minimum number of elements we need to use\nin array b, if we use sa elements in array a, in o
We pick optimal digit one by one. At each phase, let dp[sa] be the minimum number of elements we need to use\nin array b, if we use sa elements in array a, in order to obtain the optimal solution so far. We look ahead to find the next optimal digit then update dp accordingly.\n```\nclass Solution {\npublic:\n    vector<int> maxNumber(vector<int>& a, vector<int>& b, int k) {\n        int na = a.size(), nb =b.size();\n        vector<int> dp(na+1);\n        vector<int> ans;\n        while (k) {\n            int x = 0;\n            for (int sa = 0; sa <= na; ++sa) if (dp[sa] <= nb && nb- dp[sa] + na - sa >=k) {\n                for (int i = sa; i < na; ++i) if (na - i + nb- dp[sa] >= k) x = max(x,a[i]);\n                for (int j = dp[sa]; j < nb; ++j) if (na - sa + nb - j >= k) x = max(x,b[j]);\n            }\n            vector<int> dp2(na+1,INT_MAX);\n            for (int sa = 0; sa <= na; ++sa) if (dp[sa] <= nb && nb- dp[sa] + na - sa >=k) {\n                for (int i = sa; i < na; ++i) if (na - i + nb- dp[sa] >= k) if (a[i] == x) dp2[i+1] = min(dp2[i+1], dp[sa]);\n                for (int j = dp[sa]; j < nb; ++j) if (na - sa + nb - j >= k) if (b[j] == x) dp2[sa] = min(dp2[sa], j+1);\n            }\n            dp.swap(dp2);\n            ans.push_back(x);\n            --k;\n        }\n        \n        return ans;\n    }\n};\n```
[]