Maximum Sum of Non-Adjacent Elements

Problem Link: https://www.codingninjas.com/codestudio/problems/maximum-sum-of-non-adjacent-elements_843261?leftPanelTab=0

Recursion + Memoization

def maximumNonAdjacentSum(nums,size):    
    # Write your code here.
    def fun(nums,n,i):
        
        # dp[i] indicates the max sum
        # of non-adj elements from ith index
        # to (n-1)th index
        if(i==n-1):
            dp[i]=nums[n-1]
            return dp[i]
        elif(i==n-2):
            dp[i]=max(nums[i],nums[i+1])
            return dp[i]
        elif(i>=n):
            return 0
        
        if(dp[i+2]==-1):
            dp[i+2]=fun(nums,n,i+2)
        if(dp[i+1]==-1):
            dp[i+1]=fun(nums,n,i+1)
        inc=nums[i]+dp[i+2]
        exc=dp[i+1]
        dp[i]=max(inc,exc)
        return dp[i]
      
    i=0
    dp=[-1]*(size)
    return fun(nums,size,i)

Tabulation

def maximumNonAdjacentSum(nums,size):    
    # Write your code here.
    def fun(nums,n,i):
        n=size
        dp=[0]*(n)
        dp[0]=nums[0]
        if(n==1):
            return dp[0]
        dp[1]=max(nums[0],nums[1])
        if(n==2):
            return dp[1]
        for i in range(2,n):
            inc=nums[i]+dp[i-2]
            exc=dp[i-1]
            dp[i]=max(inc,exc)
        return dp[n-1]