Code Logo

Split Array Largest Sum

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Split Array Largest Sum

Solution Approach

Binary search between max(nums) and sum(nums). Feasibility: greedy split, count subarrays, compare with k.

function solution(nums, k) {
  var lo = 0, hi = 0;
  for (var i = 0; i < nums.length; i++) {
    if (nums[i] > lo) lo = nums[i];
    hi += nums[i];
  }
  function canSplit(maxSum) {
    var total = 0, count = 1;
    for (var i = 0; i < nums.length; i++) {
      if (total + nums[i] > maxSum) { count++; total = 0; }
      total += nums[i];
    }
    return count <= k;
  }
  while (lo < hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (canSplit(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Time O(n log S), Space 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;
    }
}