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.