package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/create-maximum-number/
 */
public class Problem321 {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        char[] chars = maxNumber(nums1, nums2, k, 0, 0, "", new String[nums1.length + 1][nums2.length + 1]).toCharArray();
        int[] answer = new int[chars.length];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = chars[i] - '0';
        }
        return answer;
    }

    private static String maxNumber(int[] nums1, int[] nums2, int k, int i, int j, String accu,
                                    String[][] memo) {
        if (accu.length() == k) {
            return accu;
        }
        long max = 0;
        if (i < nums1.length && j < nums2.length) {
            long a = Long.parseLong(maxNumber(nums1, nums2, k, i + 1, j + 1,
                accu + (nums1[i] > nums2[j] ? nums1[i] : nums2[j]), memo));
            long b = Long.parseLong(maxNumber(nums1, nums2, k, i + 1, j, accu, memo));
            long c = Long.parseLong(maxNumber(nums1, nums2, k, i + 1, j, accu + nums1[i], memo));
            long d = Long.parseLong(maxNumber(nums1, nums2, k, i, j + 1, accu, memo));
            long e = Long.parseLong(maxNumber(nums1, nums2, k, i, j + 1, accu + nums2[j], memo));
            max = Math.max(a, Math.max(b, Math.max(c, Math.max(d, e))));
        } else if (i < nums1.length) {
            long a = Long.parseLong(maxNumber(nums1, nums2, k, i + 1, j, accu, memo));
            long b = Long.parseLong(maxNumber(nums1, nums2, k, i + 1, j, accu + nums1[i], memo));
            max = Math.max(a, b);
        } else if (j < nums2.length) {
            long a = Long.parseLong(maxNumber(nums1, nums2, k, i, j + 1, accu, memo));
            long b = Long.parseLong(maxNumber(nums1, nums2, k, i, j + 1, accu + nums2[j], memo));
            max = Math.max(a, b);
        }
        return Long.toString(max);
    }

    public static void main(String[] args) {
        Problem321 prob = new Problem321();
        System.out.println(Arrays.toString(prob.maxNumber(new int[]{3, 4, 6, 5}, new int[]{9, 1, 2, 5, 8, 3}, 5))); // [9, 8, 6, 5, 3]
        System.out.println(Arrays.toString(prob.maxNumber(new int[]{6, 7}, new int[]{6, 0, 4}, 5))); // [6, 7, 6, 0, 4]
        System.out.println(Arrays.toString(prob.maxNumber(new int[]{3, 9}, new int[]{8, 9}, 3))); // [9, 8, 9]
        System.out.println(Arrays.toString(prob.maxNumber(new int[]{9, 8, 7}, new int[]{1, 2}, 4))); // [9, 8, 7, 2]
    }
}

@@ -36,16 +36,64 @@
 .Arrays;
+%0Aimport java.util.HashMap;%0Aimport java.util.Map;
 %0A%0A/**%0A *
@@ -306,50 +306,19 @@
 new 
-String%5Bnums1.length + 1%5D%5Bnums2.length + 1%5D
+HashMap%3C%3E()
 ).to
@@ -642,18 +642,27 @@
     
+Map%3C
 String
-%5B%5D%5B%5D
+, String%3E
  mem
@@ -727,32 +727,160 @@
 accu;%0A        %7D%0A
+        String key = accu + %22,%22 + i + %22,%22 + j;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A
         long max
@@ -2067,22 +2067,31 @@
         
-return
+String answer =
  Long.to
@@ -2103,16 +2103,70 @@
 g(max);%0A
+        memo.put(key, answer);%0A        return answer;%0A
     %7D%0A%0A 

Update problem 321