Question: 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[i] + 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?

Answer: You can solve this problem in O(n), being n the size of the array. The idea is to use Dynamic Programming to save the following information: 1 - What is the best you can make using the first i elements, if you were to pick exactly 1 element. 2 - What is the best you can make using the first i elements, if you were to pick exactly 2 elements. 3 - What is the best you can make using the first i elements, if you were to pick exactly 3 elements. To answer 1, the best you can make using the first i elements is the maximum element from the first i elements. Let's use a matrix to store that information. Let dp[1][i] be the best you can get picking exactly 1 element from the first i elements. To answer 2, the best you can make using the first i elements picking 2 elements is:  Either you do not pick the current i-th element, and get the best you could get picking exactly 2 elements up until the i-1-th element. Or you pick the current i-th element and the best you could get picking ONLY 1 element up until the i-2-th element.  Let dp[2][i] be the best you can get picking exactly 2 elements from the first i elements. It's the maximum of:  dp[2][i-1] (not picking the i-th element). A[i] + dp[1][i-2] (picking the i-th plus the best from picking 1 up until the i-2-th).  Notice that if you pick the i-th, you must NOT pick the i-1, as that would violate the rules of the problem. To answer 3, it's the same as to answer 2:  Either you do not pick the current i-th element, and get the best you could get picking exactly 3 elements up until the i-1-th element. Or you pick the current i-th element and the best you could get picking ONLY 2 elements up until the i-2-th element.  The answer will be what lies in pd[3][n-1], which means, the best you could get picking exactly 3 elements from the first n-1 elements. The code: def solution(A): n = len(A) dp = [[0] * n for i in range(4)] dp[1][0] = A[0] # The best of picking 1 element up to the 1st is the 1st. dp[2][0] = -float('inf') # You cannot pick 2 elements up to the 1st. dp[2][1] = -float('inf') # You cannot pick 2 elements up to the 2nd. dp[3][0] = -float('inf') # You cannot pick 3 elements up to the 1st. dp[3][1] = -float('inf') # You cannot pick 3 elements up to the 2nd. # Theoretically up to 4th, but the `for` already does it for you. for i in range(1, n): dp[1][i] = max( dp[1][i-1], # Either we skip the current A[i] # Or we choose it ) for i in range(2, n): dp[2][i] = max( dp[2][i-1], # Either we skip the current A[i] + dp[1][i-2] # Or we choose it ) for i in range(2, n): dp[3][i] = max( dp[3][i-1], # Either we skip the current A[i] + dp[2][i-2] # Or we choose it ) max_sum = dp[3][n-1] return max_sum