แบ่งอาร์เรย์เป็น k Subarray ให้ผลรวมมากที่สุดน้อยที่สุด (Split Array Largest Sum) ใน JavaScript

ปัญหา

รับอาร์เรย์ arr (non-negative) และ num แบ่งเป็น num subarray ต่อเนื่อง ให้ค่าสูงสุดของผลรวมแต่ละ subarray น้อยที่สุด

ตัวอย่าง

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

แบ่ง [5,1,4] (sum=10) และ [8,7] (sum=15) → ค่าสูงสุด = 15

โค้ดตัวอย่าง (Binary Search on Answer)

const arr = [5, 1, 4, 8, 7]; const num = 2; 
const splitArray = (arr = [], num = 1) => { 
  let max = 0, sum = 0; 
  const split = (arr, mid) => { 
    let part = 1, 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, 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 คำตอบ: ตรวจสอบว่าแบ่งได้กี่ส่วนถ้าจำกัดผลรวมแต่ละส่วน ≤ mid

ผลลัพธ์

15