40ms clean C++ solution


  • 1
    R
    class Solution {
    public:
    
        vector<vector<int>> dp(const vector<int>& nums)
        {
            int len = nums.size();
            vector< vector<int> > mem(len+1);
            mem[len] = nums;
            for (int i=len-1; i >=0; i--)
            {
                mem[i] = mem[i+1];
                for (int j=1; j <  mem[i].size(); j++)
                {
                    if ( mem[i][j] > mem[i][j-1])
                    {
                        mem[i].erase( mem[i].begin() + j-1);
                        break;
                    }
                }
                mem[i].resize(i);
            }
            
            return mem;
        }
    
        vector<int> special_merge(const vector<int>& res1,const vector<int>& res2, int k)
        {
                vector<int> res(k);
                int idx1=0, idx2=0, idx=0;
         
                // take the largest number. In case of equality take from the sequence that leads faster to a larger number.
                while ( idx1 < res1.size() && idx2 < res2.size())
                {
                    if (res1[idx1] > res2[idx2]) 
                    {
                        res[idx++] =  res1[idx1++];
                    }
                    else if (res1[idx1] < res2[idx2])
                    {
                        res[idx++] = res2[idx2++];
                    }
                    else
                    {
                        int tmp = res1[idx1];
                        auto r = lexicographical_compare( res1.begin() + idx1, res1.end(), res2.begin() + idx2, res2.end() )
                        ? make_pair( ref(res2), ref(idx2)) : make_pair( ref(res1), ref(idx1));
                       
                        while ( r.second < r.first.size() && r.first[r.second] == tmp)
                        {
                            res[idx++] =  r.first[r.second++];
                        }
                    }
                }
                auto it = copy(res1.begin()+idx1, res1.end(), res.begin() + idx );
                copy( res2.begin()+idx2, res2.end(), it );
                return res;
        }
        
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) 
        {
            // find best sub-sequences of nums1 and nums2 for all possible lengths
            auto mem1 = dp(nums1); 
            auto mem2 = dp(nums2);
            
            int M = min( k ,  (int) nums1.size());  // Maximum items we can take from nums1
            int m = std::max(0, k - (int) nums2.size() ); // Minimum items we can take from nums1
            
            vector<int> result;
            for (int n1 =m; n1 <= M; n1++)
            {
                result = max( result,  special_merge( mem1[ n1], mem2[k-n1], k) );
            }
            
            return result;
        }
    };

Log in to reply
 

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