# LeetCode 410: Split Array Largest Sum

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

### Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

### Note:

If n is the length of array, assume the following constraints are satisfied:

$$1 \le n \le 1000 \\ 1 \le m \le \min(50, n)$$

### Example:

Input: nums = [7,2,5,10,8] m = 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.

### Code

#include <vector>

class Solution {
public:
static int splitArray(const std::vector<int> &nums, const int m) {
size_t lo = 0;
size_t hi = 0;

for (int num : nums) {
lo = std::max(lo, (size_t) num);
hi += num;
}

while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (partitioning_is_valid(nums, m - 1, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}

return lo;
}

private:
static bool partitioning_is_valid(const std::vector<int> &nums, int partitions, size_t partition_max_sum) {
size_t accumulate_curr_partition = 0;
for (int num : nums) {
if (num > partition_max_sum) {
return false;
} else if (accumulate_curr_partition + num <= partition_max_sum) {
accumulate_curr_partition += num;
} else {
partitions--;
accumulate_curr_partition = num;

if (partitions < 0) {
return false;
}
}
}

return true;
}

};


### Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:

class Solution {
public:
int splitArray(vector<int>& nums, int m) {

}
};

• You can change the following lines in your source-code: lo = *std ::max_element(nums.begin(), nums.end()) and hi = std :: accumulate(nums.begin(), nums.end(), 0) and remove the for loop. Do make sure that to use this functions you need to include <algorithm> header file which by default is included in the Leet-Code default template. – strikersps Jul 3 '20 at 7:13

## Function signatures

You've made the best out of a slightly silly situation. I think your function signatures, while abiding to the template, have improved since the last post of yours that I reviewed.

I'm not sure whether this will break LeetCode compatibility, but if you want to enforce that no one can instantiate this class, try making a private default constructor.

## Mean

A simpler way to express the arithmetic mean than

        size_t mid = lo + (hi - lo) / 2;


is

        size_t mid = (hi + lo) / 2;

• 1 ≤ n ≤ 1000 so overflow is not an issue here unless you're using an 8-bit type, which you are not. – Reinderien Jul 2 '20 at 16:08
• On second read they leave the range of the actual array entries ambiguous? So maybe it's safe to keep the overflow-conscious version. – Reinderien Jul 2 '20 at 16:11