Float number and operators dynamic programming

FloatNumberAndOperators_dynamicProgramming.py

"""
Given a list of float numbers, and four operators +, -, *, / with flat preference, find the maximum value by inserting operator between each consecutive pair of numbers.

For example, given the array [1, 12, -3], the maximum number 33 can be found using 1 - 12 * (-3), since all operators have flat preference, so 1 - 12 * (-3) will be handled from left to right, first operation is 1 - 12 with value -11, and then second operation is -11 * (-3) = 33.


opt(i,j) = max value I can get from range i to j using all operators

opt(i, j) = max (operation <- +, -, *,/) {
                     a[i] operation opt(i+1, j-1) operation a[j]
                }
                 
    
                # 16 cases, +, + 
                 a[i] + opt(i+1, j-1) + a[j]
                 a[i] + opt(i+1, j-1) - a[j]
                 a[i] + opt(i+1, j-1) * a[j]
                 a[i] + opt(i+1, j-1) / a[j]

opt(i) = max value I can get from range 0 to i

opt_min(i) = min value I can get from range 0 to i

.....i operator  a[i]

opt(i) = max{
            opt(i-1) + a[i]
            opt(i-1) - a[i]
            opt(i-1) * a[i] # max
            opt(i-1) / a[i]
            opt_min(i-1) * a[i] # min
            opt_min(i-1) / a[i]
        }

opt_min(i) = min {}
"""

def max_value(array):
    l = len(array)
    opt = [0]*(l+1)
    opt_min = [0]*(l+1)
    
    opt[1] = array[0]
    opt_min[1] = array[0]
    
    for i in range(2, l+1):
        candidates = [opt[i-1]+a[i-1], 
                      opt[i-1]-a[i-1], 
                      opt[i-1]*a[i-1], 
                      opt[i-1]/a[i-1], 
                      opt_min[i-1]+a[i-1], 
                      opt_min[i-1]-a[i-1],
                      opt_min[i-1]*a[i-1], 
                      opt_min[i-1]/a[i-1]]
        
        opt[i] = max(candidates)
        opt_min[i] = min(candidates)
    print(opt)
    print(opt_min)
    return opt[l]

a=[1, 12, -3]
print(max_value(a))