Split array - largest sum
Google
ZetaThe problem
Given an integer array a of size n and an integer k. Split the array a into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.
Input: a = [1, 2, 3, 4, 5], k = 3 Output:6 Explanation: There are many ways to split the array a[] into k consecutive subarrays. The best way to do this is to split the array a[] into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.
Input: a = [3,5,1], k = 3 Output: 5 Explanation: There is only one way to split the array a[] into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5.
Input: a = [1, 2, 3, 4, 5], k = 2
- 1 ≤ n ≤ 104
- 1 ≤ k ≤ n
- 1 ≤ a[i] ≤ 104
cpp
class Solution {
public:
int largestSubarraySumMinimized(vector<int> &a, int k) {
}
};java
class Solution {
public int largestSubarraySumMinimized(int[] a, int k) {
}
}python
class Solution:
def largestSubarraySumMinimized(self, a, k):javascript
class Solution {
largestSubarraySumMinimized(a, k) {
}
}csharp
public class Solution
{
public int LargestSubarraySumMinimized(int[] a, int k)
{
}
}go
func largestSubarraySumMinimized(a []int, k int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Search between the maximum item and total sum.
- 02Greedily count partitions needed for a candidate limit.
- 03Start a new partition when adding an item exceeds the limit.
- 04Use partition count as the feasibility predicate.
- 05Return the first feasible limit.
Reference answer
Then expect these follow-ups
How would you reconstruct the partitions?
Tests: greedy reconstruction
Why do negative values break this approach?
Tests: assumptions
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question