Course4all
Join us on telegram
Home/dsa/Two Pointers/Split Array Largest Sum

Split Array Largest Sum

Master this topic with zero to advance depth.

Split Array Largest Sum

Given an array nums and an integer k, split the array into k non-empty contiguous subarrays such that the largest sum among these k subarrays is minimized.

nums = [7, 2, 5, 10, 8], k = 2 Possible Splits: 1. [7], [2, 5, 10, 8] -> Max Sum: 25 2. [7, 2], [5, 10, 8] -> Max Sum: 23 3. [7, 2, 5], [10, 8] -> Max Sum: 18 (Optimal!) 4. [7, 2, 5, 10], [8] -> Max Sum: 24 Binary Search Range: [Max(nums)=10, Sum(nums)=32]
Hard

Examples

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

The optimal split is [7,2,5] and [10,8], where the maximum sum of any subarray is 18.

Approach 1

Level I: Brute Force (Recursion with Memoization)

Intuition

Try every possible way to split the array into k parts and find the one that minimizes the maximum subarray sum. This can be done using recursion with memoization.

⏱ 💾 O(N * k)

Detailed Dry Run

nums=[7,2,5], k=2. Split at [7], [2,5] -> max(7, 7)=7. Split at [7,2], [5] -> max(9, 5)=9. Min is 7.

java
public int splitArray(int[] nums, int m) {
    int n = nums.length;
    int[][] memo = new int[n + 1][m + 1];
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) prefixSum[i + 1] = prefixSum[i] + nums[i];
    return solve(n, m, memo, prefixSum);
}
private int solve(int n, int m, int[][] memo, int[] prefixSum) {
    if (memo[n][m] != 0) return memo[n][m];
    if (m == 1) return prefixSum[n];
    int res = Integer.MAX_VALUE;
    for (int i = m - 1; i < n; i++) {
        int curr = Math.max(solve(i, m - 1, memo, prefixSum), prefixSum[n] - prefixSum[i]);
        res = Math.min(res, curr);
    }
    return memo[n][m] = res;
}

⚠️ Common Pitfalls & Tips

O(N^2 * k) complexity might be too slow for large N but illustrates the DP transition clearly.

Approach 2

Level II: Optimal (Binary Search on Answer)

Intuition

The 'minimized largest sum' must lie between the largest single element (since each element must belong to some subarray) and the sum of all elements (if k=1). Since the possibility of achieving a sum is monotonic (if we can achieve X, we can also achieve X+1), we can binary search this range. For each candidate sum, we greedily pack elements into subarrays.

The answer must be between max(nums) and sum(nums). Use binary search on this range. For a mid value, check if we can split the array into <= k subarrays using a greedy approach.

⏱ O(N log(Sum - Max))💾 O(1)

Detailed Dry Run

nums=[1, 2, 10], k=2. Range [10, 13]. mid=11. [1, 2], [10]. count=2. Valid. r=11. mid=10. [1, 2], [10]. count=2. Valid. r=10. Result=10.

java
class Solution {
    public int splitArray(int[] nums, int k) {
        long l = 0, r = 0;
        for (int n : nums) { l = Math.max(l, n); r += n; }
        while (l < r) {
            long mid = l + (r - l) / 2;
            if (canSplit(nums, k, mid)) r = mid;
            else l = mid + 1;
        }
        return (int)l;
    }

    private boolean canSplit(int[] nums, int k, long max) {
        int count = 1, sum = 0;
        for (int n : nums) {
            if (sum + n > max) { count++; sum = n; if (count > k) return false; }
            else sum += n;
        }
        return true;
    }
}

⚠️ Common Pitfalls & Tips

Be careful with high N and sums; using long (Java/C++/Go) is necessary to avoid overflow.

← Previous QuestionSubarrays with K Different Integers
Next Question →Maximum Sum Subarray of Size K