pythonarraysdynamic-programming

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:

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?


Solution

  • 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:

    Let dp[2][i] be the best you can get picking exactly 2 elements from the first i elements.

    It's the maximum of:

    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:

    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