Skip to main content

25. Split Array Largest Sum

hardAsked at Byju's

Partition an array into k contiguous subarrays so the maximum subarray sum is minimized.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays. Minimize the largest sum among these subarrays and return that minimum largest sum. The array contains non-negative integers.

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= min(50, nums.length)

Examples

Example 1

Input
nums = [7,2,5,10,8], k = 2
Output
18

Example 2

Input
nums = [1,2,3,4,5], k = 2
Output
9

Approaches

1. DP partition table

dp[i][j] = min largest sum splitting nums[0..i] into j parts; transition tries every split point.

Time
O(n^2 * k)
Space
O(n*k)
const n=nums.length, pref=[0];
for(const x of nums) pref.push(pref[pref.length-1]+x);
const dp=Array.from({length:n+1},()=>new Array(k+1).fill(Infinity));
dp[0][0]=0;
for(let i=1;i<=n;i++)for(let j=1;j<=k;j++)for(let p=0;p<i;p++)dp[i][j]=Math.min(dp[i][j],Math.max(dp[p][j-1],pref[i]-pref[p]));
return dp[n][k];

Tradeoff:

2. Binary search on answer

Binary search the smallest 'max-sum cap' in [max(nums), sum(nums)] for which a greedy left-to-right partition uses at most k chunks. O(n log sum) total.

Time
O(n log sum)
Space
O(1)
function splitArray(nums, k) {
  const canSplit = (cap) => {
    let chunks = 1, sum = 0;
    for (const n of nums) {
      if (sum + n > cap) { chunks++; sum = n; }
      else sum += n;
    }
    return chunks <= k;
  };
  let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b, 0);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canSplit(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Tradeoff:

Byju's-specific tips

Byju's video-tutoring scheduler partitions session blocks across tutors, so frame the binary-search-on-answer approach as a tutor-load-balancing analogy.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Split Array Largest Sum and other Byju's interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →