python - 找到给出最大总和的对，使得第二个元素在第一个之后

Question

假设我有两个长度相等的 numpy 数组:

a = np.array([1, 3, 5, 3, 2, 0])
b = np.array([1, 1, 2, 2, 4, 3])

在所有满足j >= i 的i, j 中，我如何找到i 和 j 这样

a[i] + b[j]

最大化了吗？

鉴于我的实际用例，并列的可能性很小，但如果有的话，返回最小的 i 和 j 就可以了。

Answer 1

这里是 O(n)方法:

A = np.maximum.accumulate(a)
B = np.maximum.accumulate(b[::-1])[::-1]

c = (A+B).argmax()
i = a[:c+1].argmax()
j = c + b[c:].argmax()
i,j
# (2, 4)

它是如何工作的:

我们首先引入一个额外的约束 i <= c <= j ;然后通过最大化 c 来摆脱它.

我们得到的是给定 c约束最好i和 j从 c 向后和向前看很容易找到.

谜题的最后一 block 是计算所有 c 的最佳总和的累积最大值技巧。在 O(n) .