Description Link to heading

553.optimal division

Solution Link to heading

Greedy algorithm

The optimal method is actually to bracket the penultimate elements.

Code Link to heading 

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