Solutions for largest sum of non-adjacent numbers.

    • @Geraldpof
    • @Charles, submitted in Python 3, achived 100% score
    def solve(A):
    
        n = len(A)
    
        # base case
        if n == 1:
            return A[0]
    
        # create an auxiliary space to store solutions to subproblems
        lookup = [None] * n
    
        # `lookup[i]` stores the maximum sum possible till index `i`
    
        # trivial case
        lookup[0] = A[0]
        lookup[1] = max(A[0], A[1])
    
        # traverse list from index 2
        for i in range(2, n):
    
            # `lookup[i]` stores the maximum sum we get by
    
            # 1. Excluding the current element and take maximum sum until index `i-1`
            # 2. Including the current element `A[i]` and take the maximum sum until
            #    index `i-2`
            lookup[i] = max(lookup[i - 1], lookup[i - 2] + A[i])
    
            # if the current element is more than the maximum sum until the current
            # element
            lookup[i] = max(lookup[i], A[i])
    
        # return maximum sum
        return lookup[n - 1]