algorithm - 将数组拆分为权重相似的子数组

我有一个n正数数组我需要把它分成N个相邻的子数组；n > N。
我需要最小化[max S(j) over j] - [min S(j) over j]，
其中，S(j)表示j-th子数组中元素的和。
也就是说，所有子数组都应该有“相同”的元素和。
我确信这个问题是众所周知的有人能给我指一下算法、实现或出版物吗？

最佳答案

这个问题相当于找到max S(j) over all j的最小值。
直觉：
假设所有可能的max S(j) over all j的最小值都是xmax，因此结果将是xmax - xmin。
假设，另一个ymax > xmax可以给我们提供更好的结果，这意味着ymax - yminxmax - xmin>ymin > xmin>min S(j) - ymaxmin S(j) - xmax，这是不应该发生的。
所以，问题的关键在于找到max S(j) over all j的最小值。
这可以通过使用二进制搜索来解决。
假设整个数组的总和是X，那么我们有我们的算法：

int start = 0;
int end = X;
int result = 0;
while(start <= end){
    int mid = (start + end)/2;
    for(int i = 0; i < n; i++){
       if sum of current segment > mid
           split

    }
    if total segment > N
       start = mid + 1;
    else
       update result;
       end = mid - 1;
}