将数组划分为 k 个连续分区，使得最大分区的总和最小

Question

这里最大和子集是给出最大和的 k 个子集之一，例如： arr = [10,5,3,7] 和 k = 2 将 arr 划分为 k 个子集的可能方法是

  {10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7}

和

{[10,5],[3,7} is the optimal one.

编辑：它相当于 https://www.codechef.com/DI15R080/problems/MINMAXTF

原文由 user3778989 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以在这里找到关于基于动态编程的解决方案的好文章： https ://www.geeksforgeeks.org/painters-partition-problem/ 它的复杂性是 O(k*N^2)。

为了获得更好的解决方案，您可以使用其他人建议的二进制搜索方法。您可以在此处找到使用二进制搜索的更详细的解决方案： https ://www.geeksforgeeks.org/painters-partition-problem-set-2/ 它的复杂性是 O(NlogN)

原文由 Himanshu Singh 发布，翻译遵循 CC BY-SA 4.0 许可协议