2.3 Allocation Problems

Demo: Split Array Largest Sum — LC 410 (Hard — Google High)

Statement (Demo): non-negative integer array nums এবং একটি integer k দেওয়া আছে। array-টিকে kটি contiguous non-empty subarray-তে ভাগ করতে হবে যাতে এই subarray গুলোর সর্বোচ্চ যোগফল ন্যূনতম (minimize the largest sum among these k subarrays) হয়। উদাহরণ: nums = [7,2,5,10,8], k = 2 → 18 | ⚡ n ≤ 1000, 1 ≤ k ≤ min(50, n), 0 ≤ nums[i] ≤ 10⁶

Approach: উত্তরের range: max(nums) (এক এলিমেন্টের ভাগ) থেকে sum(nums) (সব এক ভাগে)। প্রতিটা cap-এর জন্য greedy করে দেখুন কত ভাগ লাগে — k ভাগের মধ্যে হলে cap কমান।

function splitArray(nums, k) {
  const canSplit = (cap) => {
    let parts = 1,
      sum = 0;
    for (const x of nums) {
      if (sum + x > cap) {
        parts++;
        sum = 0;
      }
      sum += x;
    }
    return parts <= k;
  };
  let lo = Math.max(...nums),
    hi = nums.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (canSplit(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Complexity: Time O(n log sum), Space O(1)