Code Logo

Split Array Largest Sum

Published at24 Jul 2026
Created by
Medium 2 views
Like0

Given an integer array nums and an integer k, split nums into k contiguous non-empty subarrays such that the largest sum among these subarrays is minimized. Return the minimized largest sum. The subarrays must be contiguous — you cannot reorder elements.

This is a binary search on answer problem where the search space is between the maximum element (each element as its own subarray) and the total sum (entire array as one subarray). The feasibility check greedily splits the array: iterate through elements, accumulating a running sum. If adding the next element would exceed the candidate maximum, start a new subarray and increment the count. At the end, check if the number of subarrays needed is at most k.

The greedy partition is optimal because we are only checking feasibility of a given max sum. If we can partition into at most k subarrays with each sum <= candidate, then the candidate is feasible. The binary search finds the smallest feasible candidate.

Edge cases include k = 1 (return total sum), k = n (return max element), negative numbers (problem typically uses non-negative), and large arrays requiring careful sum calculation.

The greedy feasibility check works because splitting early (whenever the running sum exceeds the candidate) produces the maximum number of segments. If even this greedy approach stays within k segments, the candidate is definitely feasible. This property comes from the fact that splitting later never reduces the number of segments needed.

Example Input & Output

Example 1
Input
[7,2,5,10,8], 3
Output
14
Explanation

Split into 3: [7,2,5] sum=14, [10] sum=10, [8] sum=8. Largest = 14.

Example 2
Input
[1,4,4], 3
Output
4
Explanation

Each element its own subarray, max = 4.

Example 3
Input
[1,2,3], 1
Output
6
Explanation

Single subarray, sum = total.

Example 4
Input
[7,2,5,10,8], 2
Output
18
Explanation

Best split: [7,2,5] sum=14, [10,8] sum=18.

Example 5
Input
[1,2,3,4,5], 2
Output
9
Explanation

Split: [1,2,3,4] sum=10, [5] sum=5 → better: [1,2,3] sum=6, [4,5] sum=9.

Algorithm Flow

Recommendation Algorithm Flow for Split Array Largest Sum

Solution Approach

Split an array into k subarrays to minimize the largest subarray sum. Use binary search on the possible answer range between max(nums) and sum(nums). For each candidate mid, simulate a greedy split: iterate through nums, accumulate to a running sum, and start a new subarray when adding the next element would exceed mid. Count the subarrays needed. If the count is <= k, mid is feasible; try a smaller value. Otherwise, increase the lower bound.

function splitArray(nums, k) {
  var left = Math.max.apply(null, nums);
  var right = nums.reduce(function(a, b) { return a + b; }, 0);
  while (left < right) {
    var mid = Math.floor((left + right) / 2);
    var count = 1, sum = 0;
    for (var i = 0; i < nums.length; i++) {
      if (sum + nums[i] > mid) { count++; sum = 0; }
      sum += nums[i];
    }
    if (count <= k) right = mid;
    else left = mid + 1;
  }
  return left;
}

The lower bound is the largest single element (each element must go somewhere). The upper bound is the total sum (all elements in one subarray). The greedy split validation counts subarrays needed at a given capacity, and binary search finds the minimum feasible capacity.

Time complexity is O(n log sum), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int n : nums) { if (n > lo) lo = n; hi += n; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (can(nums, mid, k)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean can(int[] nums, int m, int k) {
        int total = 0, count = 1;
        for (int n : nums) {
            if (total + n > m) { count++; total = 0; }
            total += n;
        }
        return count <= k;
    }
}