# JAVA greedy & DP solution 17ms

• using dp/greedy to get all possible combination for both nums1 and nums2 then compare all the merge result to find the best one

``````public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int maxReach1 = Math.min(nums1.length, k), maxReach2 = Math.min(nums2.length, k);
List<int[]> dpNums1 = new ArrayList<int[]>(maxReach1+1), dpNums2 = new ArrayList<int[]>(maxReach2+1);
int[] empty = new int[0];
for (int i=1; i<=maxReach1; i++) dpNums1.add(getNext(nums1, dpNums1.get(i-1)));
for (int i=1; i<=maxReach2; i++) dpNums2.add(getNext(nums2, dpNums2.get(i-1)));
int x=maxReach1, y=k-x;
int[] result = new int[k];
do {
tryNextMerge(result, nums1, nums2, dpNums1.get(x), dpNums2.get(y));
} while (x-->0 && y++<maxReach2);

return result;
}
private int[] getNext(int[] nums, int[] prev) {
int position=prev.length, right = nums.length;
while(position>=0) {
int left = position>0? prev[position-1]+1 : 0;
if (left<right) {
int next = left;
for (int i=left+1; i<right; i++) if (nums[i]>nums[next]) next = i;
int[] result = new int[prev.length+1];
for (int i=0; i<position; i++) result[i]=prev[i];
result[position]=next;
for (int i=position; i<prev.length;i++) result[i+1]=prev[i];
return result;
}
right = left-1;
position--;
}
return null; //should not reach here
}
private void tryNextMerge(int[] result, int[] nums1, int[] nums2, int[] pos1, int[] pos2) {
long num = 0;
int a=0, b=0, c=0, next1= (pos1.length>0)?nums1[pos1[0]]:-1, next2 = (pos2.length>0)?nums2[pos2[0]]:-1;
boolean isBigger = false;
while (c<result.length) {
boolean from1 = false;
if (next1 > next2) from1=true;
else if (next1 == next2) {
int aa=a, bb=b, temp1 = next1, temp2 = next2;
while (temp1 == temp2 && temp1 >= next1) {
temp1 = (++aa==pos1.length) ? -1 : nums1[pos1[aa]];
temp2 = (++bb==pos2.length) ? -1 : nums2[pos2[bb]];
}
if (temp1 > temp2) from1 = true;
}
if (from1) {
if (!isBigger){
if (next1>result[c]) isBigger = true;
else if (next1<result[c]) return;
}
result[c++]=next1;
next1 = (pos1.length>++a) ? nums1[pos1[a]] : -1;
} else {
if (!isBigger){
if (next2>result[c]) isBigger = true;
else if (next2<result[c]) return;
}
result[c++]=next2;
next2 = (pos2.length>++b) ? nums2[pos2[b]] : -1;
}
}
}
}
``````

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