859. The Cheapest Tree From the Leaves

Read n positive values. Build a binary tree in which every node has either 0 or 2 children, and whose LEAVES, read left to right, are exactly those n values in order.

Every internal node is worth the product of the largest leaf in its left subtree and the largest leaf in its right subtree. Print the smallest possible total over all internal nodes. A single leaf has no internal nodes, so its answer is 0.

6 2 4 -> 32 4 11 -> 44

For 6 2 4, joining the 2 and the 4 first costs 8 and leaves a subtree whose largest leaf is 4; joining that to the 6 costs 24, giving 32. Joining the 6 and the 2 first costs 12 and then 6 * 4 = 24, giving 36, which is worse.

## The interval dynamic program, and why it is too slow

Let cost(l, r) be the answer for the leaves l .. r. Trying every split point gives

cost(l, r) = min over k of ( cost(l, k) + cost(k+1, r) + max(l..k) * max(k+1..r) )

which is O(n^3), or O(n^2) states with O(n) splits each. At n = 100000 it is hopeless, and even at n = 40 it is the obvious answer rather than the good one.

## The greedy that replaces it

Think about the SMALLEST leaf. Wherever it sits, its parent joins it to one of its two neighbours, and after that join the smallest leaf is never seen again, because the subtree containing it is represented by the larger of the pair.

So the smallest leaf should be paired with the SMALLER of its two neighbours, paying smallest * min(left neighbour, right neighbour), and then removed. Repeat.

Why is that optimal? The smallest leaf must be joined to somebody, and the price of that join is its own value times the largest leaf on the other side, which is at least the neighbour's value. Pairing it with the cheaper neighbour achieves that lower bound. Removing it afterwards leaves a strictly smaller instance, and the cost of every remaining join is unaffected, because the removed leaf was never the maximum of anything.

## The stack that runs the greedy in one pass

Keeping the array and repeatedly finding the minimum is O(n^2). A stack kept DECREASING from the bottom up does it in one pass:

push a sentinel of infinity for each value x: while the top <= x: mid = pop total += mid * min( the new top , x ) push x while more than two entries remain: total += pop * the new top

Every pop is one application of the greedy: mid is a local minimum, its two neighbours are the entry below it and x, and it is paired with the cheaper of the two. The sentinel is what lets the neighbour below always exist.

The leftover stack at the end is a decreasing run with no local minimum, so its elements are paired from the top down, each with the one below it.

## What to check

The sentinel must be larger than any possible value, and it must never be multiplied into the answer. Stopping the final loop while more than TWO entries remain is what guarantees that, since the bottom entry is the sentinel.

A single leaf answers 0, and the pop test is <= so that equal values are handled by the same greedy rather than deadlocking.

## Size

Each product reaches 10^10 and there are n - 1 of them, so the total reaches 10^15 and must be 64-bit.

## Related problems

Problem 551 is a genuine interval dynamic program of the same shape that does NOT collapse to a greedy, which is the useful contrast: the collapse here depends on the cost being a product of two maxima.

## Sizes and widths

Each product reaches 10^10 and there are n - 1 of them, so the total reaches 10^15. That is far past a signed 32 bit integer and comfortably inside a signed 64 bit one.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ a[i] ≤ 100000` - the answer can reach `10^15`, so it needs 64 bits