Given an array arr
of positive integers, consider all binary trees such that:
<li>Each node has either 0 or 2 children;</li>
<li>The values of <code>arr</code> correspond to the values of each <strong>leaf</strong> in an in-order traversal of the tree. <em>(Recall that a node is a leaf if and only if it has 0 children.)</em></li>
<li>The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.</li>
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
Example 1:
Input: arr = [6,2,4] Output: 32 Explanation: There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32. 24 24 / \ / \ 12 4 6 8 / \ / \ 6 2 2 4
Constraints:
<li><code>2 <= arr.length <= 40</code></li>
<li><code>1 <= arr[i] <= 15</code></li>
<li>It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than <code>2^31</code>).</li>