我需要写一个函数来计算数组的子数组的局部最大值的最小和，其中每个项都是可能重复的正整数。
例如，我们有一个数组[2, 3, 1, 4, 5, 6]，子数组的数量是3。我们想要得到子数组的局部最大值的最小和。这意味着，例如，将当前阵列划分为3个子阵列的一种可能方式是[[2,3], [1], [4,5,6]]，并且每个子阵列的局部最大值分别是3, 1, 6。局部最大值之和为CCD_ 5。对于这个特定的数组[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]为array[0..i](包括左边界，不包括右边界(划分为j子阵列的局部最大值的最小和。dp[0][0] = 0(这是空array[0..0]的初始值(，并且为了简单起见，用一些足够大的数字初始化所有其他dp[i][j]，以表示未计算值的无意义(在这种情况下，大于array中元素的总和就足够了(。
你的答案显然是dp[array.length][numOfSubarray]的价值。
如何计算dp的值？其实很容易。dp[i][j]是dp[k][j - 1] + max(array[k..i])中的最小值(其中k < i(。让我们分析一下这个公式：
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.length^3)(两个array.length用于两个嵌套循环，另一个因为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(长度的总和为O(n^2(。