Question

You are a brick layer, and you're trying to build a wall out of bricks. Each brick i has height 1 but can have variable length L_i .

At every step, someone hands you a brick & you have the option of either adding it to the current layer of bricks or starting a new layer of bricks on top of the old layer. Once you start a new layer of bricks, you can't add bricks to lower layers.

Each layer needs to be longer than or the same length as the one above it.

Your objective is to make this wall as tall as possible.

Give an efficient algorithm for finding the way to make a maximum wall if you must follow a predetermined sequence of bricks. (You know the sequence in advance but cannot change it). More credit for faster, correct algorithms. Note: A "greedy" algorithm won't work.

For this question, please define any subproblems and definitions you are using, state the Recurrence relation for the entries including all base cases (and explain why it's a correct recurrence relation), give the pseudocode for the alg, and analyze its Running time.

Answer 1

There are points that make possible in O(n).ˆ

consider laying the bricks from i...n.ˆ

To find the max height the subproblem can reach the is not at all enough.

There are equivalent ways to get same height, but some of them have different lengths at the bottom most layer.

ˆMinimizing the length of the bottommost layer is enough; the configuration with smallest bottommost layer will have maximum height;

To deal with the min length instead of the max height leads to a natural O(n2) dynamic programming algorithm.

We have an O(n) algorithm with an observation about how one of the indices can works.