Split Array Largest Sum

HARD

Description

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

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= k <= min(50, nums.length)

Approaches

Checkout 2 different approaches to solve Split Array Largest Sum. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a table dp[i][j] which stores the minimum largest subarray sum for splitting the first j elements of the array into i parts. The final answer is found by computing the value for splitting the entire array into k parts.

Algorithm

Define a 2D array dp[i][j] to store the minimum largest subarray sum for splitting the first j elements of nums into i subarrays.
The goal is to compute dp[k][n], where n is the length of the array.
To avoid recomputing sums, pre-calculate a prefixSum array where prefixSum[i] is the sum of elements from nums[0] to nums[i-1].
The base case is for i=1: dp[1][j] = prefixSum[j], as splitting j elements into one subarray results in the sum of those j elements.
The transition to compute dp[i][j] involves trying all possible split points p (where 0 <= p < j). The last subarray would be nums[p...j-1], and the first p elements would have been split into i-1 subarrays.
The recurrence relation is: dp[i][j] = min(dp[i][j], max(dp[i-1][p], prefixSum[j] - prefixSum[p])) for all valid p.
The final answer is dp[k][n].

In this dynamic programming approach, we define dp[i][j] as the minimum largest sum required to split the subarray nums[0...j-1] (the first j elements) into i non-empty subarrays. Our objective is to find dp[k][n], where n is the length of nums.

The state transition is formulated by considering all possible split points for the last (i-th) subarray. If we decide the i-th subarray is nums[p...j-1], then the first p elements (nums[0...p-1]) must have been optimally split into i-1 subarrays. The largest sum for this specific split would be the maximum of the sum of the last subarray (sum(nums[p...j-1])) and the result for the prefix (dp[i-1][p]). We want to choose a split point p that minimizes this value.

To make the calculation of subarray sums efficient, we pre-compute a prefix sum array. This allows us to find the sum of any subarray in O(1) time.

class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        long[][] dp = new long[k + 1][n + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Long.MAX_VALUE;
            }
        }
        dp[0][0] = 0;

        for (int i = 1; i <= k; i++) { // Number of subarrays
            for (int j = 1; j <= n; j++) { // Number of elements
                for (int p = 0; p < j; p++) { // Split point
                    long lastSum = prefixSum[j] - prefixSum[p];
                    if (dp[i - 1][p] != Long.MAX_VALUE) {
                        long currentMax = Math.max(dp[i - 1][p], lastSum);
                        dp[i][j] = Math.min(dp[i][j], currentMax);
                    }
                }
            }
        }
        return (int) dp[k][n];
    }
}

Complexity Analysis

Time Complexity: O(k * n^2), where `n` is the number of elements and `k` is the number of splits. There are three nested loops to fill the DP table.Space Complexity: O(k * n), for the 2D DP table of size `(k+1) x (n+1)` and the prefix sum array of size `n+1`.

Pros and Cons

Pros:

It is a systematic approach that guarantees finding the optimal solution.
The logic is relatively straightforward to formulate for those familiar with dynamic programming.

Cons:

The time complexity of O(k * n^2) can be too slow if n is large.
The space complexity of O(k * n) can be substantial for large k and n.

Code Solutions

Checking out 4 solutions in different languages for Split Array Largest Sum. Click on different languages to view the code.

class Solution {
public
  int splitArray(int[] nums, int k) {
    int left = 0, right = 0;
    for (int x : nums) {
      left = Math.max(left, x);
      right += x;
    }
    while (left < right) {
      int mid = (left + right) >> 1;
      if (check(nums, mid, k)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
private
  boolean check(int[] nums, int mx, int k) {
    int s = 1 << 30, cnt = 0;
    for (int x : nums) {
      s += x;
      if (s > mx) {
        ++cnt;
        s = x;
      }
    }
    return cnt <= k;
  }
}

Video Solution

Watch the video walkthrough for Split Array Largest Sum

Algorithms:

Binary Search

Patterns:

Dynamic ProgrammingGreedyPrefix Sum

Data Structures:

Array

Companies:

Tekion |PornHub |Salesforce |Zeta |