python-3.x - 给定一个间距，找到数组中最大的数字总和

Question

假设我们有一个包含一些数字的数组，并且我们得到一个值 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，因此这不是最佳答案

标签： python-3.xalgorithmsubsequencemaximization

Answer 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]