#410. 分割数组的最大值

给定一个非负整数数组和一个整数m，你需要将这个数组分成m个非空的连续子数组。设计一个算法使得这m个子数组各自和的最大值最小。

注意:
数组长度n满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

#写在前面

上次说的数组溢出问题，这次倒是没有犯了，但这次找边界条件的又是因为+1没有搞明白，其实上次就有遇到，这次一定要记住了。

#不可行方案

我最开始想到的方法是，先把子数组粗略地划分一下。

  1. 求出所有元素之和total，然后除以m得到每个子数组的平均值，记为threshold。
  2. 尽量靠近边界进行划分，比如说如果当前的和current比current + nums[i]离threshold更近，就不加，否则加。
  3. 最后一次划分的时候将所有未统计过的数字都归到最后一个子数组中。

如果说想得到一个局部最优解，那么这样的划分方法肯定没有问题，但局部最优不是全局最优，想了好久如何调整，没有思路，此方法就此作罢。

#动态规划

动态规划最重要的是要找到状态转移方程，然后确定初始条件。

令f(i)(j)为将nums[0]到nums[i]划分成j个子数组的各自和的最小值，则f(i)(j)一定可以表示为某个子划分的最小值。