Course4all

Split Array Largest Sum

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

Split Array Largest Sum

Given an integer array nums and an integer k, split the array into k non-empty contiguous subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.
Hard

Examples

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Approach 1

Level I: Dynamic Programming

Intuition

Try all possible ways to split the array using recursion with memoization. dp[i][j] represents the minimum largest sum for the subarray nums[i:] split into j parts.
⏱ $O(N^2 \\cdot K)$💾 $O(N \\cdot K)$

Detailed Dry Run

nums = [7,2,5], k=2
  • Split at index 1: max(7, 2+5=7) = 7
  • Split at index 2: max(7+2=9, 5) = 9 Min results: 7.
java
class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length, pSum[] = new int[n+1];
        for (int i=0; i<n; i++) pSum[i+1] = pSum[i] + nums[i];
        return solve(0, k, n, pSum, new Integer[n][k+1]);
    }
    private int solve(int i, int k, int n, int[] pSum, Integer[][] memo) {
        if (k == 1) return pSum[n] - pSum[i];
        if (memo[i][k] != null) return memo[i][k];
        int res = Integer.MAX_VALUE;
        for (int j=i; j<=n-k; j++) {
            res = Math.min(res, Math.max(pSum[j+1]-pSum[i], solve(j+1, k-1, n, pSum, memo)));
        }
        return memo[i][k] = res;
    }
}
Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The minimum largest sum ranges from max(nums) to sum(nums). This range is monotonic: if a max-sum XX is feasible with kk splits, X+1X+1 is also feasible. We binary search for the smallest XX.
⏱ $O(N \\cdot \\log(Sum))$💾 $O(1)$

Detailed Dry Run

StepLRMidCountDecision
11032212R = 21
21021153L = 16
31621182R = 18
Exit----Return 18
java
class Solution {
    public int splitArray(int[] nums, int k) {
        int l = 0, r = 0;
        for (int n : nums) { l = Math.max(l, n); r += n; }
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (can(nums, k, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean can(int[] nums, int k, int limit) {
        int count = 1, sum = 0;
        for (int n : nums) {
            if (sum + n > limit) { count++; sum = 0; }
            sum += n;
        }
        return count <= k;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionCapacity To Ship Packages Within D Days
Next Question →Median of Two Sorted Arrays