text: // Time:  O(k * (m + n + k)) ~ O(k * (m + n + k^2))
  // Space: O(m + n + k^2)
  
  // DP + Greedy solution.
  class Solution {
  public:
      /**
       * @param nums1 an integer array of length m with digits 0-9
       * @param nums2 an integer array of length n with digits 0-9
       * @param k an integer and k <= m + n
       * @return an integer array
       */
      vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
          const int m = nums1.size(), n = nums2.size();
          vector<vector<int>> max_numbers1(k + 1), max_numbers2(k + 1);
          maxNumberDP(nums1, max(0, k - n), min(k, m), &max_numbers1);
          maxNumberDP(nums2, max(0, k - m), min(k, n), &max_numbers2);
  
          vector<int> res(k);
          for (int i = max(0, k - n); i <= min(k, m); ++i) {
              vector<int> tmp(k);
              merge(max_numbers1[i], max_numbers2[k - i], &tmp);
              if (tmp > res) {
                  res = move(tmp);
              }
          }
          return res;
      }
  
  private:
      void maxNumberDP(vector<int> nums, int start, int end, vector<vector<int>> *max_numbers) {
          (*max_numbers)[end] = maxNumber(nums, end);
          for (int i = end - 1; i >= start; --i) {
              (*max_numbers)[i] = deleteNumber((*max_numbers)[i + 1]);
          }
      }
  
      vector<int> maxNumber(const vector<int>& nums, int k) {
          vector<int> res;
          int drop = nums.size() - k;
          for (const auto& num : nums) {
              while (drop > 0 && !res.empty() && res.back() < num) {
                  res.pop_back();
                  --drop;
              }
              res.emplace_back(num);
          }
          res.resize(k);
          return res;
      }
  
      vector<int> deleteNumber(const vector<int>& nums) {
          vector<int> res(nums);
          for (int i = 0; i < res.size(); ++i) {
              if (i == res.size() - 1 || res[i] < res[i + 1]) {
                  res.erase(res.begin() + i);
                  break;
              }
          }
          return res;
      }
  
      void merge(const vector<int>& vec1, const vector<int>& vec2, vector<int> *res) {
          auto first1 = vec1.begin(), last1 = vec1.end(),
               first2 = vec2.begin(), last2 = vec2.end();
          auto result = res->begin();
          while (first1 != last1 || first2 != last2) {
              if (greater(first1, last1, first2, last2)) {
                  *result++ = *first1++;
              } else {
                  *result++ = *first2++;
              }
          }
      }
  
      template<typename IT>
      bool greater(IT first1, IT last1, IT first2, IT last2) {
          while (first1 != last1 && first2 != last2 && *first1 == *first2) {
              ++first1;
              ++first2;
          }
          return (first2 == last2) || (first1 != last1 && *first1 > *first2);
      }
  };
  