[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)，代码如下：

对于搜索类的题目，如果我们知道答案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))，常数空间，代码如下：