一个序列分成 n 段，要求各段和的差值的最大值最小

Question

一个序列分成 n 段，要求各段和的差值的最大值最小
或者说，要求各段和尽可能接近序列和 S / n

需要最优解，思路或者代码都行

实际应用场景（免得被说是作业题）：规划瀑布流排版

---

关于 @建安七子 的原回答

可以看到第 3 步完成后确实可以近似划分成 n 个和接近的子序列，但是我认为不能还原成原顺序

（而我需要的是子串）

---

找到的资料：

https://math.stackexchange.co...

Answer 1

这是一个np问题, 要最优解只能穷举, 不然就随便想个贪心策略就行了.(比如shuffle 100次,取结果最好的那一次)

Answer 2

一个简单方法的思路
序列排序，从大到小往N个桶里面放，每次找桶内和最小的那个桶放当前值，循环至最后
会有误差，但在瀑布流排版这个场景下很小，只要不出现几个极大值想加大于等于总和1/2的情况，这个方法就可用
数量越多误差越小

https://segmentfault.com/a/11...

如果是子串问题的话
现在能想到的是用S/n作为标尺，来衡量字串是否接近均值
边界用均值或者中位数之类加上字串和占比来判断边界是否可以扩张
到达边界的时候无论是否可以扩张都反向找前面的字串检查边界是否可以移动
只要进行了移动当前字串就重新找边界
直到边界不扩张且前面字串的边界也都不可移动，算当前字串处理完成处理下一个子串