Tìm số lớn nhất từ hai mảng trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào hai mảng chữ số đơn arr1, arr2 đại diện cho hai số. Đối số thứ ba là num (num ≤ độ dài arr1 + độ dài arr2).

Hàm trả về mảng chữ số đơn độ dài num đại diện cho số lớn nhất có thể tạo từ các phần tử của cả hai mảng, với điều kiện giữ nguyên thứ tự tương đối của phần tử từ cùng một mảng.

Ví dụ, nếu đầu vào là:

const arr1 = [1, 3, 4, 5, 6]; 
const arr2 = [9, 1, 2, 5, 8, 3]; 
const num = 4;

Thì đầu ra nên là:

const output = [9, 8, 6, 3];

Ví dụ minh họa

Mã thực hiện (đệ quy + memoization):

const arr1 = [1, 3, 4, 5, 6]; 
const arr2 = [9, 1, 2, 5, 8, 3]; 
const num = 4; 
const maxArray = (arr1 = [], arr2 = [], num) => { 
  const map = new Map(); 
  const match = (a, b, num) => { 
    if (map.has(a + ',' + b + ',' + num)) { 
      return map.get(a + ',' + b + ',' + num); 
    } 
    let output = []; 
    while(num > 0) { 
      let maxa = -Infinity, maxai = 0; 
      let maxb = -Infinity, maxbi = 0; 
      for(let i = a; i < arr1.length && arr1.length + arr2.length - (i + b) >= num; i++) { 
        if (arr1[i] > maxa) { maxa = arr1[i]; maxai = i; } 
      } 
      for(let i = b; i < arr2.length && arr1.length + arr2.length - (a + i) >= num; i++) { 
        if (arr2[i] > maxb) { maxb = arr2[i]; maxbi = i; } 
      } 
      if (maxa === maxb) { 
        output.push(maxa); 
        let ca = map.get(a+','+(maxbi+1)+','+(num-1)) || match(a, maxbi+1, num-1); 
        let cb = map.get((maxai+1)+','+b+','+(num-1)) || match(maxai+1, b, num-1); 
        map.set(a+','+(maxbi+1)+','+(num-1), ca); 
        map.set((maxai+1)+','+b+','+(num-1), cb); 
        if (ca.join('') > cb.join('')) { 
          return [...output, ...ca]; 
        } else { 
          return [...output, ...cb]; 
        } 
      } else if (maxa > maxb) { 
        output.push(maxa); 
        a = maxai + 1; 
      } else { 
        output.push(maxb); 
        b = maxbi + 1; 
      } 
      num--; 
    } 
    map.set(a + ',' + b + ',' + num, output); 
    return output; 
  }; 
  return match(0, 0, num); 
}; 
console.log(maxArray(arr1, arr2, num));

Giải thích mã

Các bước: Dùng vòng lặp cho đến khi num còn lại cho phép. Nếu arr1 có số lớn hơn arr2, lấy số arr1 trước, ngược lại lấy arr2. Khi hai mảng có số bằng nhau, dùng đệ quy so sánh hai nhánh và chọn nhánh cho số lớn hơn.

Đầu ra

Kết quả trong console sẽ là:

[ 9, 8, 6, 3 ]