Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 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))
Add Comment
Please, Sign In to add comment