Given an array arr of positive integers, build a binary tree from the array that satisfies the following rules: each node is either a leaf with a value from arr, or an internal node whose value is the product of the largest leaf values in its left and right subtrees. Return the minimum possible sum of the values of all non-leaf nodes. Example: Input: arr = [6,2,4] Output: 32 Explanation: The optimal tree produces internal node costs 6*2 + 6*4 = 32. Pattern focus: Monotonic Increasing Stack for greedy merging.
arr = leaf values
minimum possible sum of internal node values
Example 1:
Input:
arr = [6,2,4]
Output:
32
Explanation:
Greedy merging with a monotonic stack minimizes the total cost.
Example 2:
Input:
arr = [4,11]
Output:
44
Explanation:
With only two leaves, the answer is their product.