Search for a command to run...
Initialization
Guess a ceiling for the largest subarray sum, then greedily cut a new subarray whenever the running total would exceed it. A higher ceiling means fewer cuts, so the partition count is monotonic — binary search the smallest ceiling needing at most k parts.
Binary Search on the Answer
1function countPartitions(a, maxSum) {2 const n = a.length;3 let partitions = 1;4 let subarraySum = 0;5 6 for (let i = 0; i < n; i++) {7 // Still fits in the current subarray8 if (subarraySum + a[i] <= maxSum) {9 subarraySum += a[i];10 } else {11 partitions++;12 subarraySum = a[i];13 }14 }//low: 40high: 10015 return partitions;16}17 18function largestSubarraySumMinimized(a, k) {19 let low = Math.max(...a);20 let high = a.reduce((acc, curr) => acc + curr, 0);21 22 while (low <= high) {23 const mid = Math.floor((low + high) / 2);24 const partitions = countPartitions(a, mid);25 26 // Too many partitions — raise the ceiling27 if (partitions > k) {28 low = mid + 1;29 } else {30 high = mid - 1;31 }32 }33 return low;34}