对所有 i、j 有效求和 max(Ai+Bj, Bi+Aj)

Question

给定两个长度为 N 的整数数组 A 和 B。您必须找到两个求和的值：

\n

Z=\xce\xa3 \xce\xa3 max(Ai+Bj, Bi+Aj)

\n

这是我的暴力算法

\n

\n
1. for 循环（i 到长度）
\n
2. for 循环（j 到长度）
\n
3. sum+=Math.max(A[i]+B[j], A[j]+B[i]);
\n

\n

请告诉我一个更有效的算法。

\n

Answer 1

利用 plus over max 的分配性质将总和重写为 Z = \xce\xa3i \xce\xa3j [max(Ai\xe2\x88\x92Bi, Aj\xe2\x88\x92Bj) + Bi + Bj]。然后构造 C = A\xe2\x88\x92B，对其进行排序，并返回 \xce\xa3i (2i+1)Ci + 2n \xce\xa3i Bi（使用从零开始的索引）。

\n