C++: find all lenth combination of two, then merge them,
The idea is to \n1) find max number of each single array of lenght l1, l2 first.  \n2) Then combine them to form the final largest one.   \n3) Then select the l
The idea is to \n1) find max number of each single array of lenght l1, l2 first.  \n2) Then combine them to form the final largest one.   \n3) Then select the largest combined one. \n\nStep 1 and 2 are both quite tricky to get right.\n\n```\nclass Solution {  \n    \n \n    // 54321  // find first bottom item:  3   \n    // nums2 = [9, 1, 2, 5, 8, 3], k=3, remain 3    \n    vector<int> maxNumber (vector<int>& nums1, int k)\n    {\n        int sz= nums1.size(), remove = sz-k;\n        vector<int> res ;\n        // best code structure: for + while\n        // goal: generate an all decreasing sequence: remove bottom  < next\n        for (int i=0; i< nums1.size(); i++)\n        {\n            // when to pop the stack:  back< current\n            while (res.size()>0 && res.back()< nums1[i] && remove)\n            {\n                res.pop_back(); remove--;             \n            }                              \n              res.push_back(nums1[i]);                    \n        }                \n\n        // finished : res may be too many, we only need k element        \n        // the case of all decreasing, just remove from back\n        while (remove)\n        {\n            res.pop_back(); remove--; \n        }        \n        \n        return res; \n    }\n    \n    // merge linked list problem: but tricker to handle equal case\n    // max len 2 : 6,5 \n   //  max len 3 : 9 8 3\n    vector<int> combine (vector<int>& v1, vector<int>& v2)\n    {\n        vector<int> res; \n        int p1=0, p2=0;\n        \n        while (p1<v1.size() && p2<v2.size())\n        {\n        // equal? look after until not equal, pick larger one next non equal one\n       //nums1: {6, 7}\n      // nums2: {6, 0, 4} : mistake: naive pick larger one won\'t work!!\n       // look after until not equal            \n            if (v1[p1]==v2[p2])\n            {\n                int p1n=p1+1, p2n=p2+1;\n                while (p1n<v1.size() && p2n<v2.size() && v1[p1n]==v2[p2n])\n                {\n                    p1n++; p2n++; \n                }\n                // several conditions:  p1n reach the end\n                // either one reach the end, pick any of they, No! pick the one with remains!!\n                if (p1n==v1.size() ) \n                {\n                    res.push_back(v2[p2++]);    \n                }\n                else if  ( p2n==v2.size())\n                    res.push_back(v1[p1++]);    \n                else if (v1[p1n]>v2[p2n]) // first non equal element\n                    res.push_back(v1[p1++]);    \n                else\n                    res.push_back(v2[p2++]);                        \n            }\n            else if (v1[p1]>v2[p2])\n                res.push_back(v1[p1++]);\n            else\n                res.push_back(v2[p2++]);\n        }\n        \n        while (p1<v1.size())\n            res.push_back(v1[p1++]);\n        \n        while (p2<v2.size())\n            res.push_back(v2[p2++]);    \n        \n        assert (res.size()== v1.size()+v2.size());\n        return res;\n    }\n\npublic:\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {       \n      \n          vector<int> max_res (k, 0); //min value     \n        for (int l1=0; l1<= nums1.size(); l1++) //select 0 to max from nums1\n        {     \n            if (k-l1<0 ) break;    // l1 too large, we stop       \n            if (k-l1> nums2.size()) continue;  // l1 too small, we continue\t\t\t\n            vector<int> m1= maxNumber (nums1, l1); \n            vector<int> m2= maxNumber (nums2, k-l1);            \n            vector<int> merge1= combine (m1, m2);          \n\n           if (merge1>max_res)\n                max_res= merge1;                        \n        }          \n        return max_res; \n    }\n};\n\n```\n\n
[]