难度 MEDIUM
给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。

示例：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释:
1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
说明:

输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。

解题思路：数组中n个数字，如果不加括号就是：

x1 / x2 / x3 / ... / xn

那么我们如何加括号使得其值最大呢，那么就是将x2后面的除数都变成乘数，比如只有三个数字的情况 a / b / c，如果我们在后两个数上加上括号 a / (b / c)，实际上就是a / b * c。而且b永远只能当除数，a也永远只能当被除数。同理，x1只能当被除数，x2只能当除数，但是x3之后的数，只要我们都将其变为乘数，那么得到的值肯定是最大的，所以就只有一种加括号的方式，即:

x1 / (x2 / x3 / ... / xn)

这样的话就完全不用递归了，这道题就变成了一个道简单的字符串操作的题目了

代码 t100 s85 java

class Solution {
    public String optimalDivision(int[] nums) {
        StringBuffer sb = new StringBuffer();
        int len = nums.length;
        for(int i=0; i<len; i++){
            if(i==0){
                sb.append(String.valueOf(nums[i]));
                if(len>1){                    
                    sb.append("/");
                }
                if(len>2){
                    sb.append("(");
                }
            }
            else if(i==len-1){
                sb.append(String.valueOf(nums[i]));
                if(len>2){
                    sb.append(")");
                }
            }else{
                sb.append(String.valueOf(nums[i]));
                sb.append("/");
            }
        }
        return sb.toString();
    }
}

代码 t100 s100 cpp

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        string res = "";
        int n = nums.size();
        for(int i=0; i<n; i++){
            if(i>0) res += "/";
            if(i==1 && n>2) res += "(";
            res += to_string(nums[i]);
            if(i==n-1 && n>2) res += ")";
        }
        return res;
    }
};

参考资料：

553. 最优除法