分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k，你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

约定

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

输入

• nums：非负整数数组
• k：要分成的连续子数组个数

输出

在所有合法划分中，k 个子数组各自和的最大值的最小值。

示例一

输入：

nums = [7,2,5,10,8], k = 2

输出：

18

解释：一共有四种分法。最优划分是 [7,2,5] 和 [10,8]，两个子数组的和分别为 14 和 18，最大和为 18。

示例二

输入：

nums = [1,2,3,4,5], k = 2

输出：

9

解释：最优划分是 [1,2,3] 和 [4,5]，最大和为 9。

示例三

输入：

nums = [1,4,4], k = 3

输出：

4

解释：最优划分是 [1]、[4]、[4]，最大和为 4。

复杂度要求

• 时间复杂度：O(n log(sum(nums)))，n 为数组长度
• 空间复杂度：O(1)