算法求解，数组划分求各划分和中的最大值最小

Question

比如我有数组a[9]={10,20,30,40,50,60,70,80,90}（这里的例子是递增的，但是不代表所有的样例都是递增或者递减的，样例是无规律的正数），然后划分成三个单独的数组，分两种情况，一种情况是保持原有顺序的划分，另外一种是可以乱序的划分，对于前者 如果把10 30划在一起，20必然也在一起。最后要得到一个结果使得各组数组中和的最大值最小，比如上面对于保持原有顺序的划分就是10,20,30,40,50|60,70|80,90 这个值就是170。问一下大家对于保持顺序和不保持顺序的两种划分方式的最优算法。

Answer 1

保序问题

保持顺序的划分问题先找个简单的例子。比如把数列1,2,3,4,5,6划分成3组，则最后一组可能有1-4个元素：

• [12345]6

• [1234]56

• [123]456

• [12]3456

然后在这4种划分中选一个最优的（如果有并列最优则任取一个）即可。中括号[]里面是一个更小规模的问题（把数列划分成两组）。由此可总结出一个递归算法。

给定数列a[1], a[2], ... a[m]，记A[i,j] = a[i], a[i+1], ... a[j]。函数groups(A[1,m],n)给出一个将数列划分成n组的最优划分。例如：

groups({1,2,3,4,5,6}, 3) = {{1, 2, 3}, {4, 5}, {6}}

递归公式为：

groups(A[1,m], 1) = {A[1,m]}
groups(A[1,m], n) = min {groups[A[1,i-1], n-1] + A[i,m]}, n <= i <= m

其中“+”表示将右边的数列作为最后的分组附加到左边的分组结果上，min是选出最优分组的操作（最大分组和最小）。

以下是Mathematica实现，缓存了中间结果（memoization）。

测试：

不保序问题

不保序的划分问题称为Multi-way partition problem，是NP-hard。 stackexchange上有个类似的问题和解答，参见这里。

Answer 2

整个数组求和后除以组数，得到的就是平均每组的和。

1、打乱顺序就是背包问题，最大值为150。

2、不打乱顺序的前提是从小到大或者从大到小的排列。应该从两段往中间分组，前面循序求和取大于平均值的和小于等于平均值的两组数，并与平均数计算差值。后面也是如此，判断四个组合中差值最小的一个取出来作为一个分组。剩下重复前面的操作。

以题面给定数组举例
每组平均值为(10+20+30+40+50+60+70+80+90)/3=150;
第一轮计算：
前面两值：10+20+30+40+50=150 10+20+30+40+50+60=210 150与平均值差为0，210与平均值差为60。
后面两值：90,90+80=170。 90与平均值差值60，170与平均值差值20。

取差值最小的0划分为一个组：10，20，30，40，50。

第二轮，剩下的60，70，80，90
前面两值：60+70=130, 60+70+80=210。与平均值150差小的是60,70的组合为20。
后面后面两值：90, 90+80=170 与平均值差值小的是90，80的组合差值20。

最后可以得出分组10，20，30，40，50|60，70|80，90。最大值为170

Answer 3

你好。假设所有数非负。
不保持顺序的情况显然不比划分问题简单，而划分问题是NPC的，所以暂时没有强多项式复杂度的解法。背包即可。
保持顺序的情况可以先预处理前缀和sum[1]..sum[n]，sum[0]=0，二分答案ans，求出最大的l使sum[l]<=ans和最小的r使sum[n]-sum[r]<=ans，如果sum[r]-sum[l]<=ans则ans合法，时间复杂度O(n+log(sum[n])*logn)。