>给定一个由数字组成的数组(数组大小为 10^5(，您需要将数组划分为 K 分区 (k<=500(，使得每个分区的最小元素之和最大
假设数组包含 A1，A2，A3......。一 现在 f(x( = min(a1，a2..ax( + min(a(x+1(，a(x+2(...啧( +...a(z+1(....一(n(
现在 f(x( 应该是最大值
其中分区必须是连续的。
所需复杂性 .(不适用(
我只是简单地一一固定了最大元素，并试图看看是否可以将其划分为K分区，如果是，我计算了f(x(
当分区数i时，让dp[i] = f(x)其中 f(x( 由 OP 定义 让我们现在开始解决它 - 基本案例-
dp[n]=sum(array elements);
//ie when number of partitions is n we return sum of elements as each element is in different partition
现在
dp[i-1] = dp[i] - min of partition collapsed in this step
因此，现在我们只需要找到每一步都需要折叠的分区。这可以通过蛮力来完成，方法是一次占用两个相邻的分区，并注意哪个分区的崩溃最不利(可以在 O(n( 中完成(。
因此，总体时间复杂度为 O(n*n-k(，空间复杂度为 O(n(。好吧，这仅限于任何可以帮助提高的人的技能。