给定一个包含 N 个整数的数组，返回 3 个不相邻元素的最大和？

Question

所以我在编码面试中遇到了这个问题，并且我一直在寻找最佳解决方案。额外的细节/限制：

• 最小数组必须为 5（因为索引 0,2,4 处的元素相加就是答案）

还有一些例子： 测试示例：[8, -4, -7, -5, -5, -4, 8, 8] 预期为 12，因为在索引 0、5、7 处，最大和为 8 + -4 + 8 = 12)

测试示例：[-2, -8, 1, 5, -8, 4, 7, 6] 预计 15 b/c 在索引 3,5,7 处，最大总和为 15)

测试示例：[-3, 0, -6, -7, -9, -5, -2, -6] 索引 1,3,6 处预计为 -9 b/c，最大总和为 -9)

测试示例：[-10, -10, -10, -10, -10] 索引 1,3,5 处预计为 -30 b/c，最大总和为 -30)

这是我目前的强力解决方案：

def solution(A):
    # Implement your solution here
    # res = []
    max_sum = -float('inf')
    n = len(A)
    for i in range(n):
        for j in range(i + 2, n):
            for k in range(j + 2, n):
                temp_sum = A[i] + A[j] + A[k]
                if temp_sum >= max_sum:
                    max_sum = temp_sum
                    # res = [i, j, k]
    return max_sum

但是，我想知道是否有更优化和更高效的方法？谢谢！

Answer 1

您可以将一些小的效率应用到您的算法中，如下所示：

def process(lst):
    m = float('-inf')
    for i in range(len(lst)-2):
        ii = lst[i]
        for j in range(i+2, len(lst)-1):
            jj = lst[j]
            for kk in lst[j+2:]:
                m = max(m, ii+jj+kk)
    return m