# 321 Create Maximum Number

給兩個整數array，和一整數k，用這兩個array組成最大的k位數（同array內的數字順序必須保持相同）

Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output:
[9, 8, 6, 5, 3]

Concept
可以切分成幾個子問題：

1. 最後產生的數字要是k位數，假如nums1佔i位，num2就必定佔k-i位
2. nums1能生成的最大i位subarray是什麼; nums2能生成的最大k-i位subarray是什麼
3. nums1和nums2的subarray能組合出來的最大數字是什麼
4. 根據不同i的組合會產生不同的最大數字，其中最大者即是答案

根據以上子問題可以產生pseudocode如下

Pseudocode

Main():
    int largestNum = Integer.MIN_VALUE
    for(int i=0; i<=k; i++){
        int[] sub1 = findLargestSubarray(nums1, i);
        int[] sub2 = findLargestSubarray(nums2, k-i);
        int currentLargest = findLargestNum(sub1, sub2);
        getLargestNum(largestNum, currentLargest);
    }

    return largestNum

findLargestSubarray():
    use a list to save i numbers, always compare with list's last ones until meet number > self, keep list size of i

findLargestNum():
    two pointer, when p1 > p2, put into result

getLargestSum():
    compare all digits in two arrays

Implementation
最後實作時，發現負責組合兩個subarray的findLargestNum()有問題。原本我沒有特別處理兩個pointer指到的數字相同的狀況，直接取num2的數字，後來發現錯誤出現在這個case: [6,7] [6,0,4] k=5. 先拿了num2的6之後，num1就會先拿6再拿7。

這時候我寫的code如下

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int l1 = nums1.length, l2 = nums2.length;
        int[] largestNum = new int[k];
        for(int i=Math.max(k-l2, 0); i<=Math.min(k, l1); i++){
            int[] sub1 = findLargestSubarray(nums1, i);
            int[] sub2 = findLargestSubarray(nums2, k-i);
            int[] currentLargest = findLargestNum(sub1, sub2);
            largestNum = getLargest(largestNum, currentLargest);
        }

        return largestNum;
    }

    private int[] findLargestSubarray(int[] num, int k){
        if(k == 0 || k > num.length) return null;
        List<Integer> resList = new ArrayList<>();
        int[] res = new int[k];;
        int drop = num.length-k;
        for(int i=0; i<num.length; i++){
            while(drop > 0 && resList.size()>0 && num[i] > resList.get(resList.size()-1)){
                resList.remove(resList.size()-1);
                drop--;
            }
            resList.add(num[i]);
        }

        for(int i=0; i<k; i++){
            res[i] = resList.get(i);
        }
        return res;
    }

    private int[] findLargestNum(int[] num1, int[] num2){
        if(num1 == null || num1.length == 0) return num2;
        if(num2 == null || num2.length == 0) return num1;
        int l1= num1.length, l2=num2.length;
        int l = l1 + l2;
        int[] res = new int[l];
        int p1=0, p2=0, pr=0;
        while(pr<l){
            if(p1 == num1.length || p2 == num2.length){
                break;
            }
            if(num1[p1] >= num2[p2]){
                res[pr] = num1[p1];
                p1++;
                pr++;
            }else{
                res[pr] = num2[p2];
                p2++;
                pr++;
            }
        }

        while(p1 < num1.length){
            res[pr] = num1[p1];
            pr++; p1++;
        }

        while(p2 < num2.length){
            res[pr] = num2[p2];
            pr++; p2++;
        }

        return res;
    }

    private int[] getLargest(int[] num1, int[] num2){
        if(num1 == null)    return num2;
        if(num2 == null)    return num1;
        int k = num1.length;
        int i=0, j=0;
        for(int m=0; m<k; m++){
            if(num1[i] > num2[j]){
                return num1;
            }else if(num2[j] > num1[i]){
                return num2;
            }
            i++; j++;
        }
        return num1;
    }
}

看起來有點太長，並且findLargestNum無法處理num1和num2相等的case。

後來我直接參考其他人的做法: https://leetcode.com/problems/create-maximum-number/discuss/77285/Share-my-greedy-solution

比起我的code更加簡化的部分是，最終getLargest和將兩subarray合併的findLargestNum用到相同的邏輯，省去findLargestNum整個function，並且活用++ operator，減少宣告的變數量。

pseudocode(new)

Main():
    for(i=Math.max(k-l2, 0); i<=Math.min(k, l1); i++)
        int[] currentLarget = merge(findLargestSubarray(nums1, i), findLargestSubarray(nums2, k-i))
        if(greater(currentLargest, 0, ans, 0){
            ans = currentLargest;
        }

    return ans;

merge():
    for(r=0; r<k; ; r++)
        ans[r] = greater(num1, i, num2, j) ? num1[i++] : num2[j++]
    return ans;

greater():
    while(i < l1, j<l2, num1[i] == num2[j])
        i++; j++;
    return j==l2 || (i<l1 && num1[i] > num2[j])

findLargestSubarray():
    two pointer, i point to num, j point to ans. 
    go through all int in num, whenever num[i] < ans[j-1], 
    we should replace ans[j-1] with num[i] and keep length of ans as k all the time.

code(new)

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int l1 = nums1.length, l2 = nums2.length;
        int[] ans = new int[k];
        for(int i=Math.max(k-l2, 0); i<= Math.min(k, l1); i++){
            int[] currentLargest = merge(findMax(nums1, i), findMax(nums2, k-i), k);
            if(greater(currentLargest, 0, ans, 0))  ans = currentLargest;
        }
        return ans;
    }

    private int[] merge(int[] num1, int[] num2, int k){
        int[] ans = new int[k];
        int i=0, j=0;
        for(int r=0; r<k; r++){
            ans[r] = greater(num1, i, num2, j) ? num1[i++] : num2[j++];
        }

        return ans;
    }

    private boolean greater(int[] num1, int i, int[] num2, int j){
        int l1 = num1.length, l2 = num2.length;
        while(i < l1 && j < l2 && num1[i] == num2[j]){//notice: here should be **while** instead of if
            i++; j++;
        }

        return (j == l2) || (i < l1 && num1[i] > num2[j]);
    }

    private int[] findMax(int[] nums, int k){
        int[] ans = new int[k];
        int len = nums.length;
        int i, j;
        for(i = 0, j = 0; i < len; i++){
            while(len - i + j > k && j > 0 && nums[i] > ans[j-1]) j--; //notice: be careful with > , <
            if(j < k)   ans[j++] = nums[i];
        }

        return ans;
    }
}