3 ms·
I think it's much more clear if you start by trying to apply the constraint to the brute force algorithm. The water container area is the distance the two side
by ninjinxo 7y ago
I think it's much more clear if you start by trying to apply the constraint to the brute force algorithm.
The water container area is the distance the two sides are apart (width), by the height of the shorter side [therefore, the longer side acts to mimic it].
Doing brute force on array $[n_1 n_2 ... n_k]$;
You'd naturally start at $n_1$ and calculate volume $V(n_1, n_k)$ and work your way inwards calculating each volume. However, if at any point $n_1$ is the shorter side, then the secondary side $n_j$ now mimics $n_1$ in height; and therefore, any new side closer to $n_1$ cannot increase the height of the container (but would decrease the width, and therefore area).
Then you'd continue the same with $n_2$, breaking iteration when $n_2$ becomes the shorter side or if $n_2$ cannot develop a greater area than $n_1$ did (either n_1 > n_2 or oldArea > n_2 * width).
etc.