arrays - 找出两个排序数组的最大总和

Question

有两个等长的排序数组A和B，其中A按升序排序，数组B 降序排列。

A = {1, 3, 7, 7, 7, 7}
B = {7, 7, 5, 5, 5, 4}

我的任务是找到两个元素，一个来自A，另一个来自B，使它们的总和最大。

有一个约束，我可以从 A 中选择任何元素，但我必须按照这样的顺序从 B 中选择元素，即数组元素的索引B 应该大于 A 的所选元素。

在这种情况下，可以选择的最大和是12。我通过简单地从左到右迭代在 O(n) 中完成了它。

我想知道是否存在更好、更有效的方法来求出这两个元素的总和。

Answer 1

我们知道，最好的和是A和B两两相加得到的序列C中的最大值。

A和B是单调的，但是C可以是任意的，所以没有捷径，需要计算整个C，O(N) 是最优的。