# Python, Exhaustive Approach with Explanation

• Let's find the indices of the N-1 divisions that take place. For example, in [1000, 100, 10, 2], the divisions are path = [1, 1, 0] (Note that subsequent indices are relative to the smaller array.)

Example:
[1000, 100, 10, 2]: divide at 1
[1000, (100/10), 2]: divide at 1
[1000, (100/10/2)]: divide at 0
path = [1, 1, 0]

To find this path, we'll consider i to be the location of the next division. Then all the stuff before A[i] is divided in the normal way, and then A[i] is divided by A[i+1], as in the expression flat(A[:i]) + flat(A[i:i+2]) + A[i+2:]. We'll take the path with the max value.

Once we found the path, to form the string, we need to ignore redundant parentheses. We do this by converting repeated values to a parentheses range "(i, j)". For example, [1, 1, 0] will convert to [(1, 3), (0, 1)]. By "(1, 3)", we mean that we should parenthesize the elements from indices 1 to 3. Because of the order that we've considered the path, repeated values will occur iff we are doing a "redundant" division from left to right of adjacent elements. We then convert our token list to the new values: for example, the first move "(1, 3)" leaves us with the token list ['1000', '(100/10/2)'].

``````def optimalDivision(self, A):
tokens = map(str, A)
A = map(float, A)

def flat(A):
if not A: return []
for x in A[1:]:

def search(A, path = []):
if len(A) == 1: return A[0], path
return max( search( flat(A[:i]) + flat(A[i:i+2]) + A[i+2:], path + [i])
for i in xrange(len(A) - 1) )

_, path = search(A)

for i, v in itertools.groupby(path[:-1]):
j = i + len(list(v))
tokens = tokens[:i] + ['({})'.format('/'.join(tokens[i:j+1]))] + tokens[j+1:]

return '/'.join(tokens)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.