我需要编写一个函数来计算数组的子数组的局部最大值的最小和，其中每个项目都是可能重复的正整数。
例如，我们有一个数组[2，3，1，4，5，6]，子数组的数量是3。我们想得到子数组的局部最大值的最小和。这意味着，例如，将当前数组划分为3个子数组的一种可能方法是[[2,3]，[1]，[4,5,6]，每个子数组的局部最大值分别是3，1，6。局部最大值的和是＜code＞3 1 6＝10＜/code＞。对于这个特定的数组，[2，3，1，4，5，6]，这是它所有可能的子数组变量的最小和。
我的方法是首先获取给定数组的所有可能的子数组变体。并得到它们的最小总和。
function getSubarrays(array, numOfSubarray) {
const results = []
const recurse = (index, subArrays) => {
if (index === array.length && subArrays.length === numOfSubarray) {
results.push([...subArrays])
return
}
if (index === array.length) return
// 1. push current item to the current subarray
// when the remaining items are more than the remaining sub arrays needed
if (array.length - index - 1 >= numOfSubarray - subArrays.length) {
recurse(
index + 1,
subArrays.slice(0, -1).concat([subArrays.at(-1).concat(array[index])])
)
}
// 2. start a new subarray when the current subarray is not empty
if (subArrays.at(-1).length !== 0)
recurse(index + 1, subArrays.concat([[array[index]]]))
}
recurse(0, [[]], 0)
return results
}
function getMinSum(arrays) {
return arrays.reduce(
(minSum, array) =>
Math.min(
minSum,
array.reduce((sum, subarray) => sum + Math.max(...subarray), 0)
),
Infinity
)
}
getMinSum(getSubarrays([[2,3], [1], [4,5,6]], 3)) // 10
然而，我认为我的解决方案的时间复杂度非常高。我的猜测是，这是2^n的订单(如果我错了，请随时纠正我)。不知道有没有更高效的方法来计算这个。
首先想到的是动态编程。
让dp[i][j]是数组[0… i]（包括左边框，不包括右边框）的局部最大值的最小和，分为j子数组。dp[0][0]=0（这是空数组[0…0]的初始值），为了简单起见，用一些足够大的数字初始化所有其他dp[i][j]表示没有意义的未计算值（在这种情况下大于数组中元素的总和就足够了）。
你的答案显然是dp[array. long][numOfSubarray]的值。
你如何计算 dp 的值？其实很容易。dp[i][j] 是 dp[k][j - 1] max（array[k..i]） （其中 k
dp[k][j - 1] + max(array[k..i])
# ^ ^
# This term is the minimal sum of local maximums
# of array[0..k] divided into j-1 subarrays.
# |
# This term is maximum of your new j-th subarray.
还要确保事先计算了所有的 dp[k][j - 1]（例如，首先计算 dp[i][1]，然后计算 dp[i][2]，然后计算 dp[i][3]，依此类推）。
现在让我们完全写它（现在只是天真的方法）。
dp[0][0] = 0
for newSubarrayNumber in range(1, numOfSubarray + 1):
for previousEnd in range(0, array.length):
for newEnd in range(previousEnd + 1, array.length + 1):
# Formula from above.
dp[newEnd][newSubarrayNumber] =
min(dp[newEnd][newSubarrayNumber],
dp[previousEnd][newSubarrayNumber - 1] + max(array[previousEnd..newEnd]))
# Your answer.
print(dp[array.length][numOfSubarray])
如您所见，我们得到了多项式复杂度，现在是O（numOfSubarray*array. long^3）（两个array.long用于两个嵌套循环，还有一个是因为max（array[previousEnd…newEnd]））。
我们还可以优化我们的算法。总是计算min（array[previousEnd… newEnd]）是没有意义的，因为之前我们对newEnd-1这样做了，我们可以重用该值。这将我们带到以下算法：
for newSubarrayNumber in range(1, numOfSubarray + 1):
for previousEnd in range(0, array.length):
maxElement = 0
for newEnd in range(previousEnd + 1, array.length + 1):
# maxElement replaces max(array[previousEnd..newEnd]).
maxElement = max(array[newEnd - 1], maxElement)
dp[newEnd][newSubarrayNumber] =
min(dp[newEnd][newSubarrayNumber],
dp[previousEnd][newSubarrayNumber - 1] + maxElement)
那是 O（numOfSubarray * array.length^2）（只是因为循环，没有额外的复杂性乘数）。
我相信人们可以进一步优化它（也许使用一些高级数据结构），请随意评论。对于这个特定的问题，更好的方法可能是某种贪婪的算法（比如让小子数组靠近数组的边界，在中心放一个大块，但这需要证明）。
我们可以通过使用动态程序得到O(n^2，其中状态是(1)到目前为止所考虑的最右边元素的索引，以及(2)结束于(1)的子数组的长度。
我们需要存储的关于这两件事的信息是确定性的——我们需要子数组 （2） 中的最大值和以 （1） 结尾的总体最佳解决方案。
然后，为了考虑下一个元素，对于 （2） 中的每个长度，我们有两个选择：要么将元素添加到子数组中，要么开始一个新的子数组。
对于每个元素，我们将检查总O(n^2).的O(n)长度
