Учитывая массив из N целых чисел, верните максимальную сумму трех несмежных элементов. ⇐ Python

[Anonymous]

Мне задали этот вопрос на собеседовании по программированию (шутка, это часть клуба соревновательного программирования моего университета, так как немногим людям любопытно, лол), и я застрял в поиске оптимального решения. Дополнительные детали/ограничения:

• минимальный массив должен быть равен 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]
ожидалось -9 b/c при индексах 1,3,6, максимальная сумма равна -9)Пример теста: [-10, -10, -10, -10, -10]
ожидается -30 b/c при индексах 1,3,5, максимальная сумма - -30)< /p>
Вот мое текущее решение методом перебора:

Код: Выделить всё

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

Есть ли что-нибудь более оптимальное и эффективное?

Подробнее здесь: https://stackoverflow.com/questions/771 ... t-elements