LR - DP

arr1=[8,15,3,7]

def max_profit(arr,n):
    
    memo={}
    def solve(i,j):
        # base case 
        if i>j or i>=n or j<0:
            return 0 
        k=(i,j)
        # memo 
        if k in memo:
            return memo[k]
        
        
        # recursion 
        option1=arr[i]+ min(solve(i+2,j),solve(i+1,j-1))
        option2=arr[j]+ min(solve(i+1,j-1),solve(i,j-2))
        memo[k]=max(option1,option2)
        # return
        return memo[k]
    return(solve(0,n-1))
print(max_profit(arr1,4))