Medium

Quiz

#553 Optimal Division

APPROACH

You are given an integer array nums whose elements will be joined by division operators evaluated left-to-right without parentheses.

- For example, nums = [2,3,4] gives the expression "2/3/4".

You may insert parentheses anywhere to change the evaluation order in order to maximize the resulting value. Return the parenthesized expression string that achieves the maximum value. Do not include any redundant parentheses.

Example 1:

Input: nums = [1000,100,10,2]

Output: "1000/(100/10/2)"

Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200

However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.

So you should return "1000/(100/10/2)".

Other cases:

1000/(100/10)/2 = 50

1000/(100/(10/2)) = 50

1000/100/10/2 = 0.5

1000/100/(10/2) = 2

Example 2:

Input: nums = [2,3,4]

Output: "2/(3/4)"

Explanation: (2/(3/4)) = 8/3 = 2.667

It can be shown that after trying all possibilities, we cannot get an expression with evaluation greater than 2.667

1 of 4

1:00

What is the optimal approach for this problem?