MALI2017_MAXCOST.py

'''
https://www.codechef.com/MALI2017/problems/MAXCOST

Sample Input1:
5
1
3
1
5
2
Output:
43

'''




n = int(input())
wines = list()
for i in range(n):
    wines.append(int(input()))

# creating n*n bytearra
mc = [[-1 for x in range(n)] for x in range(n)]

######################
# Bottom-Up approach #
######################

# draw the recursion tree for better understanding of the code..

age=n
# if only one wine remains.., its age will defenitely be 'n'
for i in range(n): 
    mc[i][i] = wines[i]*age

for l in range(2,n+1): # L:no of remaing wines.. 
    age = age-1
    # for each possible number of wines('L') that remains in shelf 
    for i in range(n-l+1): 
        j = i+l-1
        mc[i][j] = max(wines[i]*age+mc[i+1][j], wines[j]*age+mc[i][j-1])

print(mc[0][n-1])


#####################
# top-Down approach #
#####################

# def prob(s, e, age):
#     if mc[s][e]>=0:
#         return mc[s][e]
#     if s==e:
#         return wines[s]*age
#     mc[s][e] = max(wines[s]*age + prob(s+1,e,age+1), wines[e]*age + prob(s,e-1, age+1))
#     return mc[s][e]

# print(prob(0,n-1,1))

# for lst in mc:
#     print(lst)