Sponsored
Sponsored
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.
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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int splitArray(vector<int>& nums, int k) {
7 int maxElem = *max_element(nums.begin(), nums.end());
8 int sum = accumulate(nums.begin(), nums.end(), 0);
9 int left = maxElem, right = sum;
10 while (left < right) {
11 int mid = left + (right - left) / 2;
12 int currentSum = 0, pieces = 1;
13 for (int num : nums) {
14 if (currentSum + num > mid) {
currentSum = num;
pieces++;
} else {
currentSum += num;
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}The C++ solution finds the maximum element and total sum of the input array, setting these as the bounds for binary search. It iteratively narrows down the search range, checking if the current middle point can be split into ≤ k subarrays. The result is the required minimized largest sum, which the function returns.
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.
Time Complexity: O(n^2 * k), as each subproblem depends on earlier solutions.
Space Complexity: O(n*k), for the dp table.
1
public class Solution {
public int SplitArray(int[] nums, int k) {
int n = nums.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[,] dp = new int[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0;
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n; i++) {
for (int p = 0; p < i; p++) {
dp[j, i] = Math.Min(dp[j, i], Math.Max(dp[j - 1, p], prefix[i] - prefix[p]));
}
}
}
return dp[k, n];
}
}C# employs the same principles employed in other languages, using tuples as dp keys and exploring all legitimate breakpoints during iterations. This solution efficiently builds comprehensive pathways to determine suitable subdivisions and manage max sums.