Split Array Largest Sum

Master this topic with zero to advance depth.

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 $X$ is feasible with $k$ splits, $X+1$ is also feasible. We binary search for the smallest $X$ .

⏱ $O(N \\cdot \\log(Sum))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Count	Decision
1	10	32	21	2	R = 21
2	10	21	15	3	L = 16
3	16	21	18	2	R = 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;
    }
}

← Previous QuestionCapacity To Ship Packages Within D Days

Next Question →Median of Two Sorted Arrays

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.