I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.
I need to find the least possible balance of any full binary tree with $x_1,x_2,\cdots,x_n$ as the weights of its leaves. I don't need to output the tree, just the value.
I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node:
For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is:
I am looking for some hints as to what the sub-problems might be.