arrays - 在数组中找到两个总和最大的非后续元素 - 面试问题

Question

问题类似于here ， 除了:

我们正在寻找最大值。

答案可以包含数组的第一个或最后一个元素(但不能同时包含两者 - 因为我们认为它们是相邻的)。

我的尝试:

我想在上面的链接中使用与 RomCoo 相同的想法，但将其调整为这个问题:

找出最大的数。

找到不是第一个邻居的第二大。然后建立总和。

计算第一个数字的两个邻居的总和。检查它是否大于第一个总和。
如果不是:取第一个和，否则取第二个。

我相信步骤 (2) 和 (3) 上的对是唯一可以得出最大和的对，但我无法正式证明这一点。
如果这是正确的，你如何正式证明它？
如果没有，你如何解决它？

Answer 1

假设我们有两个数字 A和 B构成更大的总和。要么A或 B (或两者)不得与最大数直接相邻，否则它们将落入(3)。让我们把它当作 A ，不失一般性。自 A不与我们最大的数相邻，则B如果还没有，可以安全地替换为我们最大的数字，从而导致更大的总和。因此，要达到最大值，B必须等于我们最大的数字。同理，如果存在大于 A 的值不与我们最大的数相邻，那么这个和也不会是最大的，所以 A必须是第二大数字。这意味着 A和 B将落入(2)。因此，(2)和(3)是我们唯一有效的解决方案。