Minimize the Largest Sum of Exactly k Contiguous Parts
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Minimize the Largest Sum of Exactly k Contiguous Parts
Split an array `nums` into exactly `k` nonempty contiguous subarrays. Every element must belong to one part, and the original order must be preserved.
Return the smallest possible value of the largest part sum.
### Function
`int splitArray(vector<int>& nums, int k)`
### Example 1
```text
Input: nums = [5,1,4,2], k = 2
Output: 6
```
The split `[5,1] | [4,2]` has sums `6` and `6`. Their maximum is `6`, and two part sums adding to `12` cannot both be smaller than `6`.
### Example 2
```text
Input: nums = [0,0,7,0], k = 3
Output: 7
```
One valid split is `[0] | [0] | [7,0]`. The part containing `7` cannot have a sum below `7`.
### Constraints
- `1 <= nums.length <= 1000`.
- `0 <= nums[i] <= 1000000`.
- `1 <= k <= min(50, nums.length)`.
### Clarifications
Parts cannot be empty and cannot skip elements. Zero-valued elements are allowed. Return the minimized largest sum, not the split boundaries. The task requires exactly `k` parts, even when several partitions achieve the same value.
### What a Strong Answer Covers
- Contiguity, complete coverage, and the exact number of nonempty parts.
- Zero values, one part, and one element per part when allowed.
- Why no partition can have a smaller largest sum.
- Correctness, arithmetic safety, and resource bounds.
Overview: Practice splitting a nonnegative array into exactly a specified number of nonempty contiguous parts while minimizing the largest part sum. Handle zeros and boundary cases.