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

Question

问题与此处类似，此外：

1. 我们正在寻找最大值。
2. 答案可以包含数组的第一个或最后一个元素（但不能同时包含两者——因为我们认为它们是相邻的）。

我的尝试：

我想在上面的链接中使用与 RomCoo 相同的想法，但针对这个问题进行调整：

1. 找出最大的数。
2. 找到不是第一个邻居的第二大的。然后建立总和。
3. 计算第一个数字的两个邻居的总和。检查它是否大于第一个总和。如果不是：取第一个总和，否则取第二个。

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

标签： arraysalgorithmtime-complexitymax

Answer 1

我猜这个问题“有点”类似于 1031 LeetCode 问题，你可以在这个链接中看到它：

Python

class Solution:
    def maxSumTwoNoOverlap(self, nums, l, m):
        for index in range(1, len(nums)):
            nums[index] += nums[index - 1]
        largest = nums[l + m - 1]
        l_max, m_max = nums[l - 1], nums[m - 1]
        for index in range(l + m, len(nums)):
            l_max = max(l_max, nums[index - m] - nums[index - l - m])
            m_max = max(m_max, nums[index - l] - nums[index - l - m])
            largest = max(largest, l_max + nums[index] - nums[index - m], m_max + nums[index] - nums[index - l])

        return largest

爪哇

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int l, int m) {
        for (int index = 1; index < nums.length; index++)
            nums[index] += nums[index - 1];

        int largest = nums[l + m - 1];
        int lMax = nums[l - 1];
        int mMax = nums[m - 1];

        for (int index = l + m; index < nums.length; index++) {
            lMax = Math.max(lMax, nums[index - m] - nums[index - l - m]);
            mMax = Math.max(mMax, nums[index - l] - nums[index - l - m]);
            largest = Math.max(largest, Math.max(lMax + nums[index] - nums[index - m], mMax + nums[index] - nums[index - l]));
        }

        return largest;
    }
}

对于您的问题，您必须在扫描阵列时保持至少 2 的距离，以便处理相邻部分。例如，您在扫描时最大化index和或和。index + 2index - 2index

参考

这是 lee215 在 Java/Python/C++ 中的回答