Maximum adjacent product sum (Interview question)

We have an array of integers where integer in each position is seen as its value. Each time a position is selected, you will earn the amount associated with it multiplied by its adjacent position's value (left and right side). After a position has been selected it would be removed from the array and its left and right positions would become adjacent to each other.

If there are no adjacent positions assume a value of 1 for the same. For example, if there is only single position left and you select it then it's value will be multiplied by 1 as both left and right adjacent positions.

Find out what can be maximum amount earned at the end after selecting all positions.

I have implemented a dynamic programming approach to it using the following recurrence relation : First we observe that if we somehow in the process as mentioned in question encounter a step where we multiply arr[position_p] and arr[position_q], then all positions in between position_p and position_q should have already been chosen, if any.
For simplicity let us assume array indices start from 1 and position 0 and position n+1 contain value 1 in accordance with the question, where n is the number of elements in array. So we need to select positions p+1 to q-1 in such an order that maximizes the amount.

Using this, we obtain recurrence relation :
If f(p,q) is maximum amount obtained by choosing only from positions p+1 to q-1, then we have :
f(p, q) = max ( f(p,k) + f(k,q) + arr[p] * arr[k] * arr[q] ) for k between p and q (Excluding p and q) where k is last position chosen from positions p+1 to q-1 before choosing either p or q

And here is the python implementation :

import numpy as np 

n = int(input("Enter the no. of inputs : "))

arr = [1]
arr = arr + list( map( int, input("Enter the list : ").split() ) ) 
arr.append(1)

# matrix created to memoize values instead of recomputing
mat = np.zeros( (n+2, n+2), dtype = "i8" )

# Bottom-up dynamic programming approach
for row in range ( n + 1, -1, -1 ) :

    for column in range ( row + 2, n + 2 ) :

        # This initialization to zero may not work when there are negative integers in the list.
        max_sum = 0

        # Recurrence relation 
        # mat[row][column] should have the maximmum product sum from indices row+1 until column-1
        # And arr[row] and arr[column] are boundary values for sub_array 
        # By above notation, if column <= row + 1, then there would be no elements between them and thus mat[row][column] should remain zero

        for k in range ( row + 1 , column ) :

            max_sum = max( max_sum, mat[row][k] + mat[k][column] + ( arr[row] * arr[k] * arr[column] ) )

        mat[row][column] = max_sum

print(mat[0][n+1])

Edit : Though this is no proof, as suggested by @risingStark I have seen the same question on LeetCode also where all correct algorithms seem to have used O(n^2) space running in O(n^3) time for general case solution.