对于 i>j，x_i + y_j 的最大值

Question

假设我们有两个数组，x_1,...,x_n 和 y_1,...,y_n。通过首先在 O(n) 中找到两个数组的最大元素然后将其求和，可以在 O(n) 中计算两个数组的最大成对和：

max_{i,j} x_i + y_j = max_i x_i + max_j y_j

但是，如果我们想找到最大值使得 x_i 和 y_j 的索引不减少，我不确定我们是否可以在小于 O(n^ 2) 通过列举所有的可能性。

max_{i>j} x_i + y_j

有谁知道如何在 O(n log n) 最坏情况复杂度下执行此操作？谢谢

Answer 1

我明白了。考虑这个算法：

sum_max = -Inf;
y_max = -Inf;

for i in 1:n do
y_max = max(y_max,y_i)
sum_max = max(x_i+y_max,sum_max)

return sum_max

由于 n 次应用了 2 个元素的最大操作，复杂度为 O(n)。

Answer 2

此代码将解决您的问题，它是一个复杂度为 O(n) 的解决方案。我们可以看到 $$\max_{i > j} x_i + y_j = \max_{i} x_i + \max_{i > j} y_j$$

int ymax = y[0], res = y[0] + x[1];

for(int i = 1; i < len; ++i){
    res = max(res, ymax + x[i]);
    if(i < ylen) ymax = max(ymax, y[i]);
}

Maximum of x_i + y_j for i>j