**Problem:**

Please find the problem here.

**Analysis:**

This is a good problem, I spent some good time thinking about solving it.

The key idea is that finding the solution is hard, but guessing one isn't. The solution must be somewhere between $ -1 < x < sum $

If we had a way to tell if the answer is bigger of smaller than the actual solution, then we can binary search the answer.

**Solution:**

The question above basically turn into a feasibility question. Is it feasible to split the array such that the maximum sum is at most $ x $? We can solve this problem using a simple greedy assignment.

Walking from the beginning of the array, pick as much element as we can to fit the sum less than $ x $ constraint, and then pick the another segment, and so on. If we can get this in $ m $ segment, it is feasible, otherwise it is not.

We can use a simple exchange argument to prove that this is a valid test. If there exists a feasible split, we can always move the splitting boundary right when it is feasible, eventually, that will lead to a solution that would have been found by our greedy splitting.

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/split-array-largest-sum/ #include "LEET_SPLIT_ARRAY_LARGEST_SUM.h" #include <map> #include <algorithm> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_SPLIT_ARRAY_LARGEST_SUM { class Solution { public: int splitArray(vector<int>& nums, int m) { long long total = 0; for (size_t i = 0; i < nums.size(); i++) { total += nums[i]; } // lo is always infeasible // hi is always feasible long long lo = -1; long long hi = total; while (lo + 1 < hi) { long long mid = lo + (hi - lo) / 2; long long run = 0; int seg = 1; for (size_t i = 0; i < nums.size(); i++) { if (run + nums[i] <= mid) { run += nums[i]; } else { if (nums[i] > mid) { seg = m + 1; break; } i--; seg++; run = 0; } } if (seg <= m) { hi = mid; } else { lo = mid; } } return hi; } }; }; using namespace _LEET_SPLIT_ARRAY_LARGEST_SUM; int LEET_SPLIT_ARRAY_LARGEST_SUM() { Solution solution; vector<int> input; input.push_back(1); input.push_back(2147483646); cout << solution.splitArray(input, 2) << endl; return 0; }

## No comments :

## Post a Comment