## Saturday, October 8, 2016

### LeetCode OJ - Split Array Largest Sum

Problem:

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