/Python/Stickler Thief or Maximum sum such that no two elements are adjacent

Stickler Thief or Maximum sum such that no two elements are adjacent

Recursion :
def FindMaxSum(arr, n):
        
    def recur(arr, n):
        
        if n == 1:
            return arr[n-1]
        
        if n == 2:
            return max(arr[n-1], arr[n-2])
        
        return max(recur(arr, n-1), recur(arr, n-2) + arr[n-1])
    
    return recur(arr, n)
 
Top Down :
def FindMaxSum(arr, n):
        
    def top_down(arr, n, dp):
        
        if dp[n] != -1:
            return dp[n]
    
        dp[n] =  max(top_down(arr, n-1, dp), top_down(arr, n-2, dp) + arr[n-1])
        
        return dp[n]
    
    if n == 1:
        return arr[0]
    if n == 2:
        return max(arr[0], arr[1])
        
    dp =[-1 for i in range(n+1)]
    dp[1] = arr[0]
    dp[2] = max(arr[0], arr[1])
    
    return top_down(arr, n, dp)
  
Bottom Up :
def FindMaxSum(arr, n):
        
    def bottom_up(arr, n, dp):
        
        for i in range(2, n):
            dp[i] =  max(dp[i-1], dp[i-2] + arr[i])

    if n == 1:
        return arr[0]
    if n == 2:
        return max(arr[0], arr[1])
        
    dp =[0 for i in range(n)]
    dp[0] = arr[0]
    dp[1] = max(arr[0], arr[1])
    
    bottom_up(arr, n, dp)
    
    return dp[n-1]

Source: practice.geeksforgeeks.org

Similar codes

0 vote345 views1 answer
Deleting models with sqlalchemy orm
Python
3 votes331 views1 answer
Static root django
Python Django
0 vote324 views1 answer
Read://https_www.tumblr.com/?url=https://www.tumblr.com/login?redirect_to=%2Fneue_web%2Fiframe%2Freblog%2F629907744681590784%2FjQw7OUs8&3739a18c-0c68-43cc-a4cb-b8b99e9bfd72=a52e06db-92b6-4b86-b3c5-fa2ab267405c
Python
3 votes320 views1 answer
Print the heat map python
Python
0 vote334 views1 answer
Picobot python
Python
0 vote369 views1 answer
Isolationforest estimators
Python
0 vote276 views1 answer
Parallel run of a function with multiple arguments partial
Python
0 vote354 views1 answer
Python remove dtype from array
Python
0 vote445 views1 answer
Get a list of ids from queryset django
Python Django
75 votes355 views4 answers
Download pip install
Python