ชุดย่อยที่มีผลรวมสูงสุดใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของจำนวนเต็ม ฟังก์ชันของเราต้องการหาชุดย่อยขององค์ประกอบที่ไม่ติดกันที่มีผลรวมสูงสุด

และสุดท้าย ฟังก์ชันควรคำนวณและคืนค่าผลรวมของชุดย่อยนั้น

ตัวอย่างเช่น

ถ้าอินพุทอาร์เรย์คือ

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

ผลลัพธ์ควรเป็น 20 เพราะชุดย่อยที่ไม่ติดกันของตัวเลขจะเป็น 3, 7 และ 10

ตัวอย่างโค้ด

โค้ดสำหรับการทำงานนี้จะเป็นดังนี้

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));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็นดังนี้

20