Tập con có tổng lớn nhất trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận một mảng số nguyên. Hàm được yêu cầu tìm tập con của các phần tử không liền kề với tổng lớn nhất.

Và cuối cùng, hàm sẽ tính và trả về tổng của tập con đó.

Ví dụ –

Nếu mảng đầu vào là:

const arr = [3, 5, 7, 8, 10];

Thì đầu ra nên là 20 vì tập con không liền kề của các số sẽ là 3, 7 và 10.

Ví dụ

Mã thực hiện:

const arr = [3, 5, 7, 8, 10];
const maxSubsetSum = (arr = []) => {
  let min = -Infinity;
  const helper = (arr, ind) => {
    if ( ind < 0 ){ return min };
    let inc = helper(arr, ind-2);
    let notInc = helper(arr, ind-1);
    inc = inc == min ? arr[ind] : Math.max(arr[ind], arr[ind] + inc);
    return Math.max( inc, notInc );
  };
  return helper(arr, arr.length - 1);
};
console.log(maxSubsetSum(arr));

Kết quả

Kết quả trong console:

20