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:
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?
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:
i-th element, and get the best you could get picking exactly 2 elements up until the i-1-th element.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:
i-th element, and get the best you could get picking exactly 3 elements up until the i-1-th element.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