找到给定数组中长度最多为“k”的所有连续子数组和不连续的子数组的最大总和

Question

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

限制： 0 <=

arr.size()

<= 10^5; 0 <=

arr[i]

<= 10^5; 1 <= k <= 10^5;

例如：

1. arr = [1, 10, 7, 3, 4]

   和

   k = 1

   。答案是14。 解释：我们只能选择大小为 1 的子数组，因此我们将选择 [10] 和 [4]，它们的总和为 14。不能选择 [10],[7],[4]，因为 [10] 和[7] 是连续的子数组。

2. arr = [15 9 11 11 1 12 18 18 18 8 1]

   和

   k = 3

   。答案应该是94 解释：子数组为 [15], [11, 11], [12, 18], [18, 8, 1]，这些总和为 94。

这是入室抢劫者问题的更新，可以使用动态规划轻松解决：

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是删除值的索引）但有些地方出了问题。

有什么办法可以降低这个解决方案的时间复杂度吗？

感谢您抽出时间。

Answer 1

添加尺寸，然后使用最佳条纹的想法。

首先，正如@Neil建议的那样，最小化漏洞更容易。每个洞必须在前一个洞的

k+1

范围内。我们将通过保留一个由

best_holes

对组成的数组

(index of last hole, sum of 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))