Problem statement

https://leetcode.com/problems/optimal-division/

Solution 1

One of the possible solution is dp, where we have states dfs(i, j, part}, where i and j are start and end numbers and part equal to 0 or 1, where 0 means we need to maximize value and 1 means that we need to minimize value. We need this part value, because we need maximize part in the left and minimize part in the right of division. Also we need to carefully deal brackets: we need them if we are in the right part and if length of this part is more than one.

Complexity

Time complexity is O(n^3), space complexity also O(n^3), because each solution takes O(n) space.

Code

class Solution:
    def optimalDivision(self, nums):
        
        @lru_cache(None)
        def dfs(i, j, part):           
            if i == j: return [nums[i], str(nums[i])]
            cand = [0, ""] if part == 0 else [float("inf"), ""]
            for k in range(i, j):
                part1 = dfs(i, k, part)
                part2 = dfs(k+1, j, 1-part)
                res_num = part1[0]/part2[0]
                left, right = part1[1], part2[1]
    
                if k-i == 0 and k+1 != j: right = "(" + right + ")"
                
                operators = [max, min]
                cand = operators[part](cand, [res_num, left + "/" + right])

            return cand
     
        return dfs(0, len(nums)-1, 0)[1]

Solution 2

There is smarter mathematical solution, where we note, that maximum will reach at point $a_1/(a_2/a_3/\dots a_n)$. So all we need to do is deal with $n=1$ and $n=2$ cases.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def optimalDivision(self, nums):
        A = list(map(str, nums))
        if len(A) <= 2: return '/'.join(A)
        return A[0] + '/(' + '/'.join(A[1:]) + ')'