1

假设我们有一个包含一些数字的数组，并且我们得到一个值 d（其中 d >= 1），它指示某个所需的索引。我们如何找到以 d 为界的值的最大总和。这是一个例子：

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 3

将返回 4000 + 5000 = 9000（因为这两个数字之间至少有 3 的距离）。但在这种情况下：

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

将返回 4000 + 2500 + 5000 = 11500。

编辑：更多解释 - 我们需要在数组中找到最大可能的总和。唯一的技巧是我们不能包含小于 d 索引的数字。在第二个示例中，我们可以轻松地将所有数字相加以获得最大值，但由于我们以 d = 2 为界，我们必须选择一个数字不小于距离 2 的组合。另一个示例可能包括 3000 + 2500 + 5000 = 10500。如果您查看我的第二个解决方案 11500 > 10500，因此这不是最佳答案

4

2 回答 2

1

使用动态规划方法可以有效地解决这个问题。

设为A输入数组，d为间隙大小。然后，您可以构造一个数组B，使其成为 的第一个元素B[i]的最大总和。您可以通过简单的递归计算 的元素，最后一个元素包含解决方案：i+1AB

def solve(A, d):
    n = len(A)
    B = [0] * n
    B[0] = A[0]
    for i in range(1, d):
        B[i] = max(A[i], B[i-1])
    for i in range(d, n):
        B[i] = max(A[i] + B[i-d], B[i-1])
    return B[-1]
于 2021-04-18T00:48:51.443 回答
0

您可以通过迭代计算每个前缀的最佳总和来一次性完成。

一旦你有每个前缀的最佳总和，i但不包括至少远离-th 元素的元素）。iiprefix_sums[i - 1]ii + prefix_sums[i - d]idi

a = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

prefix_sums = [a[0]]
for x in a[1:]:
    cur = x if len(prefix_sums) < d else x + prefix_sums[-d]
    cur = max(cur, prefix_sums[-1])
    prefix_sums.append(cur)

print(max(prefix_sums))
于 2021-04-18T20:47:11.630 回答