493. The Tallest Pair of Equal Stacks

Blocks of given heights are to be built into TWO stacks of exactly EQUAL height. Each block may be used in one stack, the other, or left out entirely. Print the greatest height the two stacks can reach, or 0 if no non-empty equal pair is possible.

1 2 3 6 -> 6 stacks {6} and {1,2,3} 1 2 -> 0 no equal pair exists

## Why the obvious state is too big

The natural state is the pair of stack heights, which needs sum^2 entries. With heights summing to 5000 that is 2.5 * 10^7 per item and too slow.

## The state is the difference

Two stacks are interchangeable, so what matters is not which is which. And once the DIFFERENCE between them is known, together with the height of the SHORTER one, both heights are known.

dp[d] = the greatest height of the SHORTER stack, over all ways to reach difference d

The answer is dp[0], where the difference is zero and the shorter stack is therefore both of them.

The difference only ever ranges over 0 .. sum, so the table is one-dimensional. That is the trade: one dimension is bought by storing a value instead of a flag.

## The transitions

For a block of height v at difference d with shorter stack lo:

leave it out d stays, lo stays add to TALLER d becomes d+v, lo stays the shorter one did not change add to SHORTER d becomes |d-v|, lo becomes lo + min(v, d)

The third line is the one to get right. Adding v to the shorter stack raises it by v, but if v exceeds the gap d the stacks SWAP roles, and the new shorter stack is the old taller one, whose height is lo + d. Both cases are lo + min(v, d).

Writing lo + v instead is correct only while v <= d and silently overstates the shorter stack whenever a block overshoots the gap.

## Reading the answer

dp[0] starts at 0, which represents two empty stacks. That is why "no equal pair possible" and "the best equal pair has height 0" give the same output, and the statement says 0 for both rather than pretending to distinguish them.

1 2 answers 0 and 5 answers 0: in both cases the only equal pair is the empty one.

## Boundaries

4 6 10 answers 10, from {10} against {4,6}, using every block.

1 1 1 1 answers 2, from two blocks against two. Not 1: the greedy of pairing equal blocks one at a time stops early, and taking all four is better.

3 4 5 6 answers 9, from {4,5} against {3,6}, which is the case where no block is left out and no obvious pairing exists.

Heights sum to at most 5000, so the difference index is small, but the stored heights still want a 64-bit accumulator in languages where the sum could grow.

Constraints - `1 ≤ n ≤ 20` - `1 ≤ height ≤ 250` - the heights sum to at most `5000`