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 <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)This approach uses binary search to efficiently find the minimized largest sum. The range for binary search is between the maximum single element in the array (lower bound) and the sum of the array (upper bound). For each candidate middle value in the binary search, we check if it's possible to partition the array into k or fewer subarrays such that none has a sum greater than this candidate. This check is done through a greedy approach: we iterate over the array, adding elements to a running sum until adding another element would exceed the candidate sum, at which point we start a new subarray.
The C implementation first calculates the sum and maximum value of the given array. These provide the binary search boundaries. The implementation then uses a while loop for the binary search, updating the boundaries based on whether the current guess can divide the array into ≤ k subarrays. The function finally returns the minimized largest sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log(sum - max)), where sum is the total sum of array and max is the maximum element.
Space Complexity: O(1), as no additional space proportional to input size is used.
We can also use dynamic programming to solve this problem by maintaining a DP table where dp[i][j] means the minimum largest sum for splitting the first i elements into j subarrays. The recurrence is based on considering different potential previous cut positions and calculating the maximum sum for the last subarray in each case, iterating across feasible positions.
This C solution implements dynamic programming by using a dp table initialized with INT_MAX, with the exception of dp[0][0] set to 0 allowing split calculations. The recurrence is used to iterate over each possible partition configuration, minimizing the result stored at dp[k][numsSize].
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k), as each subproblem depends on earlier solutions.
Space Complexity: O(n*k), for the dp table.
| Approach | Complexity |
|---|---|
| Binary Search with Greedy Split | Time Complexity: O(n log(sum - max)), where sum is the total sum of array and max is the maximum element. |
| Dynamic Programming | Time Complexity: O(n^2 * k), as each subproblem depends on earlier solutions. |
BS 19. Painter's Partition and Split Array - Largest Sum • take U forward • 150,599 views views
Watch 9 more video solutions →Practice Split Array Largest Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor