LeetCode 410: Split Array Largest Sum

Question

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) {
 
 }
};

• Problem

• Solution

• Discuss

• strikersps: 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.

Answer 1

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;

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