ผลรวมของอาร์เรย์ย่อยที่ใหญ่ที่สุดใน JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของจำนวนเต็มที่ไม่ติดลบ arr เป็นอาร์กิวเมนต์แรก และจำนวนเต็ม, num, (num

งานของฟังก์ชันของเราคือแบ่งอาร์เรย์ออกเป็น num non-empty subarrays ต่อเนื่องกัน ควรแยกอาร์เรย์ในลักษณะที่จะลดผลรวมที่ใหญ่ที่สุดในบรรดาอาร์เรย์ย่อย num เหล่านี้ ฟังก์ชันของเราควรส่งคืนผลรวมที่ใหญ่ที่สุดที่สะสมในอาร์เรย์ย่อย

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

const arr = [5, 1, 4, 8, 7];
const num = 2;

จากนั้นผลลัพธ์ควรเป็น −

const output = 15;

คำอธิบายผลลัพธ์

แม้ว่าจะมีสี่วิธีในการแบ่งอาร์เรย์ดั้งเดิมเป็นอาร์เรย์ย่อย แต่ถ้าเราแบ่งอาร์เรย์ออกเป็นสองกลุ่ม [5, 1, 4] และ [8, 7] แล้ว ทั้งสองกลุ่มจะมีผลรวมน้อยที่สุดและกลุ่มที่ใหญ่กว่าของทั้งสองกลุ่มคือ 8 + 7 =15 ซึ่งฟังก์ชันของเราควรส่งคืน

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
   let max = 0;
   let sum = 0;
   const split = (arr, mid) => {
      let part = 1;
      let tempSum = 0;
      for (let num of arr) {
         if (tempSum + num > mid) {
            tempSum = num;
            part++;
         } else {
            tempSum += num;
         }
      }
      return part;
   };
   for (let num of arr) {
      max = Math.max(max, num);
      sum += num;
   };
   let low = max;
   let high = sum;
   while (low < high) {
      let mid = Math.floor((high+low)/2);
      let part = split(arr, mid);
      if (part > num) {
         low = mid + 1;
      } else {
         high = mid;
      }
   }
   return low;
};
console.log(splitArray(arr, num));

คำอธิบายโค้ด:

เราใช้ Binary Search เพื่อตรวจสอบว่าเราสามารถหาการแบ่งที่ดีที่สุดได้หรือไม่

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น -

15