553. Optimal Division

算法
string 
Given a list of positive integers, the adjacent integers will perform the float division. 
For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. 
You should find out how to add parenthesis to get the maximum result, 
and return the corresponding expression in string format. 
Your expression should NOT contain redundant parenthesis.

Example:
Input: [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 don't 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

这个题的思路需要先找到除法运算的规律。 a/b/c…/n 的除法，通过添加括号，使运算的结果最大。
我们可以发现，无论怎么加括号，a一定是被除数的一部分，b一定是除数的一部分。所以结果最大的时候是
$a / ( b / c /…/ n)$
这时候有 $a / ( b / c /…/ n) = a \times c \times …n / b$ ,其中被除数最大，除数最小。
找到这一个规律，这个题就很好实现了。虽然我也没有想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var optimalDivision = function(nums) {
    var result = ''
 
    if(nums.length===1){
        return String(nums[0])
    }else if(nums.length===2){
        return nums[0]+'/'+nums[1]
    }
    result = nums[0]+'/'
    var temp = ''
    for (var i=1; i<nums.length; i++){
        temp = temp + nums[i] + '/'
    }
    result = result + '(' + temp.substring(0,temp.length-1) +')'
 
    return result
};