[LeetCode]Split Array Largest Sum

假设前i个数字被切分成j个subarray，j个subarray的区间和中最大值为x，我们用DP[i][j]表示所有切分的可能中，x的最小值。我们可以有递推公式：

• dp[i][j] = min(max(dp[k][j - 1], sum(k, i - 1))), where k <= i - 1
• base case：dp[i][1] = sum(0, i - 1)

我们可以先求出presum array，这样当我们需要计算sum(k, i - 1)可以很快算得。假设输入数组array长度为n，要求切分为m个subarray，算法时间复杂度和空间复杂度均为O(n * m)，代码如下：

	class Solution {
	public:
	int splitArray(vector<int>& nums, int m) {
	int len = nums.size(), sum = 0;
	//dp[i][j] represents minimum largest sum by dividing first i characters into j subarrays
	//dp[i][j] = min(max(dp[k][j - 1], sum(k + 1, i)))
	//base case: dp[i][1] = presum[i] - 0(since we need to get dp[k][j - 1] when calculate dp[i][j]), dp[i][0] = INT_MAX, dp[0][i] = INT_MAX;
	vector<vector<int>> dp(len + 1, vector<int>(m + 1, INT_MAX));
	vector<int> preSums(1, 0);
	for(auto& num : nums){sum += num;preSums.push_back(sum);};
	for(int i = 0; i < len; ++i)
	{
	dp[i + 1][1] = preSums[i + 1] - preSums[0];
	for(int j = 2; j <= min(i + 1, m); ++j)
	{
	for(int k = i; k >= j - 1; --k)
	{
	dp[i + 1][j] = min(max(dp[k][j - 1], preSums[i + 1] - preSums[k]), dp[i + 1][j]);
	}
	}
	}
	return dp[len][m];
	}
	};

view raw Split Array Largest Sum_dp.cpp hosted with ❤ by GitHub

对于搜索类的题目，如果我们知道答案ans所在的区间[lo, hi]，并且给定一个值y，我们有比较效率的算法可以验证y是否是ans的上/下界，那么通常binary search都是值得考虑的算法。这一题也是同样，显然我们知道答案是在[max(array[i]), sum(0,  n - 1)]区间中，并且给定y，我们有O(n)的算法可以验证y是否是答案ans的上/下界：

• 我们从头开始切分array，每一次我们找到当前区间和小于y的最大值所对应的区间，如果最后切分的区间数d > m，那么我们知道y是ans的下界，因为y可以更大从而d可以更小，也就是代表ans >= y
• 如果d <= m，显然我们应该减小y让其能切分更多的subarray，也就是说y是ans的上界，ans <= y

根据以上条件我们就可以采用binary search的解法来解决这道题，时间复杂度O(n * log(sum))，常数空间，代码如下：

	class Solution {
	public:
	int splitArray(vector<int>& nums, int m) {
	long len = nums.size(), lo = LONG_MIN, hi = 0;
	for(auto& num : nums)
	{
	hi += num;
	if(num > lo)lo = num;//this guarantee that mid is always larger than nums[i]
	}
	while(lo < hi)
	{
	long mid = lo + (hi - lo) / 2;
	//we know if mid is possible upper bound of answer
	if(isUpperLimit(nums, mid, m))
	hi = mid;
	else
	lo = mid + 1;
	}
	return lo;
	}
	private:
	//if we can split array to at least m + 1 pices with upper limit mid, then the minimum max subarray value is larger than mid, otherwise, it is equal to or smaller than mid
	bool isUpperLimit(vector<int>& nums, long target, int m)
	{
	long count = 0, sum = 0;
	for(auto& num : nums)
	{
	if(sum + num > target)
	{
	sum = num;
	++count;
	}
	else
	sum += num;
	}
	return count < m;
	}
	};

view raw Split Array Largest Sum_bs.cpp hosted with ❤ by GitHub