从两个已排序的数组中找到最大的总和

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)。

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

- vivek puri

---

有没有可能在不查看至少一个数组的所有元素的情况下找到答案？ - user1196549

@fjardon，下一个（递增的）索引。 - Mark Shevchenko

@juanchopanza: 因为这是最小值;-)而我们寻找最大值 - Gombat

@Bathsheba B按降序排列，您必须选择一个大于A的索引，因此下一个索引指向B中允许的最大值，该值对应于您在A中选择的索引。 - fjardon

@fjardon: 对的，所以你要遍历所有索引，将A和B从同一个索引相加，并保存具有最大总和的索引。这是一个简单的任务，时间复杂度为O(n)。 - Gombat

Answer 1

我们知道最大的和是在将序列A和B成对相加后得到的序列C中最大的值。

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

- user1196549

---

请证明C是任意的。 - fjardon

@fjardon：没错，对于法语来说是错误的朋友。 - user1196549

@YvesDaoust 很好，我很高兴并点赞了你的回答 :) 那确实是棘手的部分。 - fjardon

参数的另一种形式：令A[i]=2i和B[i]=-2i；您可以修改一些A[k]=2k+1，这将使最大值移动到任何您喜欢的位置。 - user1196549

@YvesDaoust 没错，我表达不清楚。我说的是你最新的例子。你提出的任意序列确实是证明无法设计比 O(n) 更好的算法的基石。 - fjardon

Answer 2

正如Yves Daoust所指出的那样，原则上，O(n)是最优的，但在实践中，您可以使用一些简单的技巧来节省时间。

您可以利用A的最大值。

const int maxA = A[sizeA-1];

在你的循环中，你可以检查以下两个条件来安全地中止你的循环搜索最大值（i是你的循环变量）。

// since B will be smaller the next time and A is at its max, no need to go further
if ( A[i] >= maxA ) break; 

// if there is no chance left, to find a greater sum, since even maxA with the biggest
// B we are about to see is not big enough, break.
if ( maxA + B[i] <= currentMax ) break;

- Gombat

---

它并不一定会节省时间，因为您需要对每个元素进行两次检查（在某些情况下，这将花费更多时间）。 - Jarod42

可能是这样，我认为第一个检查不如第二个成功的可能性大。 - Gombat

@Jarod42：你说得对。无论数组中的值是什么，循环至少要运行到最大值，这个最大值平均来说是一半；而且在许多情况下，它可能会继续运行，甚至到最后。由于判断最大值是一个非常简单的操作，这些结合起来的“节省时间”的技巧代表了更高的成本效益。 - user1196549