We want to construct a stationary crane and place it on a flat roof.
We will make it by placing beams on top of each other and attaching a weightless
cable to the end of one of the beams. All the beams have the same
square cross-section but their lengths vary. Here is a picture
of a crane (with its load attached to the cable) that could be constructed using 3 beams.
==== building========= |
We have already determined the order of the beams:
the first beam must
be placed on the roof, the second beam on top of it, etc. During
construction we can support the crane, but after construction is complete
and the load is attached to the cable the resulting crane must not fall apart.
Specifically, a topmost section of the crane will tip and fall if the horizontal position of
it center of gravity is to the left or right of the beam (the roof for the entire crane) on which it rests.
We have chosen our units so that each beam's weight is the same as its
length. Given a int beam (the weights or lengths of each beam in order)
and LOAD, return the maximum overhang that we can achieve.