在给定的数组中，找到所有连续子数组的最大和，这些子数组之间不相邻，并且长度最多为'k'。

Question

在给定的数组中，找到所有连续子数组的最大和，这些子数组之间不相邻，并且长度最多为'k'。

algorithmdynamic-programming

3

问题：给定一个数组'arr'和一个整数'k'，找到所有大小不超过'k'的子数组的最大和。注意不能选择连续或重叠的子数组。

约束条件： 0 <= arr.size() <= 10^5; 0 <= arr[i] <= 10^5; 1 <= k <= 10^5;

例如：

arr = [1, 10, 7, 3, 4] and k = 1。答案将是14。解释：我们只能选择大小为1的子数组，所以我们将选择[10]和[4]，它们的和为14。你不能选择[10]，[7]，[4]，因为[10]和[7]是连续的子数组。

arr = [15 9 11 11 1 12 18 18 18 8 1] and k = 3。答案应该是94。解释：子数组是[15]，[11, 11]，[12, 18]，[18, 8, 1]，这些和为94。

这是House Robber问题的更新版本，可以通过动态规划轻松解决：

dp[i] = max(dp[i-2] + arr[i], dp[i-1])

我可以通过在动态数组中添加一个维度来解决这个问题：

dp[i][j] = max(dp[i-2][j-1] + arr[i], dp[i-1][k])

但问题是，上述解决方案在最坏情况下会超过时间限制：k = 10^5 和 arr.size() = 10^5。即使当 k = 10^4 和 arr.size() = 10^4 时，它的运行速度也非常慢，因为时间复杂度为 O(n*k)。

我尝试过从以 arr[0:k+1] 开始的子数组中移除最小值，然后继续在 arr(j+1:j+k+1)（j 是被移除值的索引）中移除，但结果出现了错误。

有没有办法降低这个解决方案的时间复杂度呢？

感谢您花费时间阅读。

- Shirina

可以给我一些澄清吗？为什么在第二个例子中您没有选择长度为3的任何子数组？为什么在第一个例子中选择了2个子数组，而在第二个例子中选择了4个子数组。问题表述不够清晰。我能想到两种合理的解释方式，但都不符合你的例子。 - Kevin

或者你可以尽量减少出现在每个“n”的空隙？ - Neil

@Neil 你是指每个 'k' 吗？我已经移除了每个 k 中的最小数，我还计算了每个 k+2 个数字中的最小和（例如：[2,4,5,3]，k=2。我将计算 arr[i] + arr[i+k+1] 并与中间子数组 [4,5] 中的每个数进行比较。如果有任何小于该和的数，我将移除它。否则，我将移除 arr[i] 和 arr[i+k+1]）。但是这些思路都没有通过所有的测试案例。你还有其他的想法吗？ - Shirina

没错，k。我只是从另一个角度看问题；如果答案正确的话，我认为使用哪个问题陈述应该无关紧要。也许我忽略了明显的东西，但你能解释一下为什么你认为“打劫房屋”问题的维度较小吗？ - Neil

1

@Neil House Robber的概念是检查抢劫这个房子的最大利润，或者选择不抢劫这个房子而去抢劫下一个房子。在这个问题中，我们不能选择连续的两个子数组，并且子数组的大小不能超过'k'，当'k' = 1时，与House Robber问题相同。这个问题唯一不同的地方是我们必须处理'k'。 - Shirina

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

添加维度，然后使用最佳边缘的概念。

首先，如@Neil所建议的那样，最小化孔洞会更容易。每个孔洞必须在前一个孔洞的k+1范围内。我们将通过保持一对(最后一个孔洞的索引，孔洞总和)的数组best_holes来实现。它以一个虚拟元素(-1, 0)开始，表示数组开始之前的一个孔洞。

如果我们可以通过放置一个稍后的孔洞来达到同样好或更好的效果，我们就不需要跟踪保留孔洞的可能性。

当最佳孔洞太早，后面没有其他孔洞时，我们也会丢弃它们。

以下是O(n)的代码。

from collections import deque

def best_sum (ary, k):
    best_holes = deque([(-1, 0)])
    for i in range(len(ary)):
        # Value of a hole at i plus the best best hole.
        value = ary[i] + best_holes[0][1]

        # Get rid of best_holes that this is better than.
        while value <= best_holes[-1][1]:
            best_holes.pop()

        # Record this best hole.
        best_holes.append((i, value))

        # Get rid of the best hole if it is too old to be used directly.
        if k < i - best_holes[0][0]:
            best_holes.popleft()

    return sum(ary) - best_holes[0][1]

print(best_sum([1, 10, 7, 3, 4], 1))
print(best_sum([15, 9, 11, 11, 1, 12, 18, 18, 18, 8, 1], 3))

如果你想知道哪些数组组成了这个和，只需使用以下链表技巧：

def best_arrays (ary, k):
    best_holes = deque([(-1, 0, None)])
    for i in range(len(ary)):
        # Value of a hole at i plus the best best hole.
        value = ary[i] + best_holes[0][1]

        # Get rid of best_holes that this is better than.
        while value <= best_holes[-1][1]:
            best_holes.pop()

        # Record this best hole.
        best_holes.append((i, value, best_holes[0]))

        # Get rid of the best hole if it is too old to be used directly.
        if k < i - best_holes[0][0]:
            best_holes.popleft()

    answer = []
    i = len(ary)
    best_hole = best_holes[0]
    while -1 < i:
        if best_hole[0] + 1 < i:
            answer.append(ary[best_hole[0]+1 : i])
        i = best_hole[0]
        best_hole = best_hole[2]
    return list(reversed(answer))