[Python] Given an array of N integers, return the max sum of 3 NON-adjacent elements

I got this question for a coding interview (mock, part of my uni's competitive programming club since a few people are curious lol), and I got stuck on finding the optimal solution. Extra details/constraints:

• minimum array has to be 5 (because the elements at index 0,2,4 summed would be the answer)

And some examples: Example test: [8, -4, -7, -5, -5, -4, 8, 8] expected 12 because at indices 0, 5, 7, max sum is 8 + -4 + 8 = 12)

Example test: [-2, -8, 1, 5, -8, 4, 7, 6] expected 15 b/c at indices 3,5,7, the max sum is 15)

Example test: [-3, 0, -6, -7, -9, -5, -2, -6] expected -9 b/c at indices 1,3,6, the max sum is -9)

Example test: [-10, -10, -10, -10, -10] expected -30 b/c at indices 1,3,5, max sum is -30)

Here's my current brute force solution:

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 + A[j] + A[k]
if temp_sum >= max_sum:
max_sum = temp_sum
# res = [i, j, k]
return max_sum


Is there anything more optimal and efficient?

Continue reading...