max-subset-sum-no-adjacent.py

# Max Subset Sum No Adjacent
# https://www.algoexpert.io/questions/Max%20Subset%20Sum%20No%20Adjacent
#
# Write a function that takes in an array of positive integers
# and returns the maximum sum of non-adjacent elements in the array.
#
# If a sum can't be generated, the function should return `0`.
#
# Input:
# A = [75, 105, 120, 75, 90, 135]
#
# Output:
# 330 // 75 + 120 + 135

# Recurrence:
# let A = array of numbers
# let N = length of A
# f(i) when i >= N -> 0;
# f(i) when i == 0 -> max(A[i], f(i + 1));
# f(i) when i == 1 -> max(A[i - 1] + f(i + 1), A[i] + f(i + 2));
# f(i) -> max(A[i] + f(i + 2), f(i + 1)).

from typing import List, Tuple

# Recursive: O(2^N) time | O(N) space
def fRecursive(A: List[int]) -> int:
    N: int = len(A)
    def f(i: int) -> int:
        if i >= N:
            return 0
        elif i == 0:
            return max(A[i], f(i + 1))
        elif i == 1:
            return max(A[i - 1] + f(i + 1), A[i] + f(i + 2))
        else:
            return max(A[i] + f(i + 2), f(i + 1))
    return f(0)

# Top Down: O(N) time | O(N) space
def fTopDown(A: List[int]) -> int:
    N: int = len(A)
    dp: List[int] = [None] * (N + 2)
    def f(i: int) -> int:
        if dp[i] is not None:
            return dp[i]
        else:
            if i >= N:
                dp[i] = 0
            elif i == 0:
                dp[i] = max(A[i], f(i + 1))
            elif i == 1:
                dp[i] = max(A[i - 1] + f(i + 1), A[i] + f(i + 2))
            else:
                dp[i] = max(A[i] + f(i + 2), f(i + 1))
            return dp[i]
    return f(0)
    
# Bottom Up: O(N) time | O(N) space
def fBottomUp(A: List[int]) -> int:
    N: int = len(A)
    dp: List[int] = [None] * (N + 2)
    for i in range(N + 2)[::-1]:
        if i >= N:
            dp[i] = 0
        elif i == 0:
            dp[i] = max(A[i], dp[i + 1])
        elif i == 1:
            dp[i] = max(A[i - 1] + dp[i + 1], A[i] + dp[i + 2])
        else:
            dp[i] = max(A[i] + dp[i + 2], dp[i + 1])
    return dp[0]

# Bottom Up: O(N) time | O(1) space
def fBottomUpZeroSpace(A: List[int]) -> int:
    N: int = len(A)
    dp_1: int = 0
    dp_2: int = 0
    dp_i: int = 0
    for i in range(N)[::-1]:
        if i >= N:
            dp_i = 0
        elif i == 0:
            dp_i = max(A[i], dp_1)
        elif i == 1:
            dp_i = max(A[i - 1] + dp_1, A[i] + dp_2)
        else:
            dp_i = max(A[i] + dp_2, dp_1)
        dp_2 = dp_1
        dp_1 = dp_i
    return dp_i

if __name__ == '__main__':
    tests: List[Tuple[List[int], int]] = [
        ([75, 105, 120, 75, 90, 135], 330),
        ([], 0),
        ([1], 1),
        ([1, 2], 2),
        ([1, 2, 3], 4),
        ([1, 15, 3], 15)
    ]
    for A, expected in tests:
        print(f'A = {repr(A)}')
        for func in (fRecursive, fTopDown, fBottomUp, fBottomUpZeroSpace):
            challenge = func(A)
            if challenge != expected:
                print(f'{func.__name__} returned {challenge}, which is not the expected: {expected}')