# C++ Two Clean and Short Solutions: Binary Search & Traditional DP,

• ``````/// O(log2(high - low)*n), where low high are defined as in the program below:
struct Solution {
int splitArray(vector<int>& nums, int m) {
long long low = INT_MIN, high = 0;
for (int n : nums)
high += n, low = max<long long>(low, n);
low = max(low , high / 50);
while (low < high)
{
long long mid = low + (high - low) / 2;
if (test(nums, m, mid))
high = mid;
else
low = mid + 1;
}
return high;
}
bool test(vector<int>& nums, int m, long long bar)
{
int sum = 0, count = 1;
for (int n : nums)
if (sum + n > bar)
{
sum = n;
count ++;
if (count > m)
return false;
}else
sum += n;
return true;
}
};

///O(mn^2) dp slow but short;
struct Solution {
int splitArray(vector<int>& nums, int m) {
vector<long long> sums(nums.size() + 1), dp (nums.size());
for (int i = 0; i < nums.size(); ++i)
dp[i] = sums[i + 1] = sums[i] + nums[i];
for (int k = 2; k <= m; ++k)
for (int i = nums.size() - 1; i >= k - 1; --i)
for (int j = k - 2; j < i ; ++j)
dp[i]= min(dp[i], max(dp[j], sums[i + 1] - sums[j + 1] ));
return dp[nums.size() - 1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.