Maximum Number of Books You Can Take

Maximum Number of Books You Can Take

What is this problem about?

The Maximum Number of Books You Can Take coding problem gives you shelves with a given number of books. You want to choose a contiguous segment of shelves and take as many books as possible, subject to the constraint that the number of books taken from each shelf must form a strictly increasing sequence from left to right, and from each shelf you can take at most as many books as are on it.

Why is this asked in interviews?

Amazon includes this problem because it requires a non-obvious combination of monotonic stack with dynamic programming. The constraint — strictly increasing, bounded above by shelf count — means that for any right endpoint, you need to efficiently find the optimal left starting point. The monotonic stack prunes impossible left endpoints, while DP computes the maximum books for each right endpoint.

Algorithmic pattern used

Monotonic stack + DP: For each right endpoint r (the last shelf), the books taken form the sequence books[r], books[r]-1, books[r]-2, ..., books[r]-k+1 for some k, going left from r. The sequence is constrained by each shelf's capacity: you can't take more than books[i] from shelf i.

Use a monotonic stack to find, for each r, the leftmost valid start l where books[l] >= books[r] - (r - l). For the valid segment, sum the arithmetic progression. The DP value dp[r] = sum of taken books with r as the last shelf.

Example explanation

Shelves: [8, 5, 2, 7, 2, 6] For r=5 (books=6), taking sequence going left: 6, 5, 4, ... but shelf at index 4 has only 2 books, so you can take at most 2 from it. The sequence would be: take 6 from shelf 5, 5 from shelf 3 (wait, they must be contiguous).

• Contiguous from r=5: can take up to [2, 3, 4, 5, 6] for indices [4, 3, 2, 1, 0] going back, but capped by shelf counts [2, 7, 2, 5, 8]. So [2, 3, 2, 3, 4] — but must be strictly increasing. Shelf 2 (value 2) < shelf 1 (value 5) requirement but capped to 2, breaking strict increase.

The monotonic stack finds the valid segment boundary efficiently. DP[r] = max books for all valid starting points.

Common mistakes candidates make

• Not enforcing strict increase: Taking the same count from two shelves violates the constraint.
• Forgetting the upper bound per shelf: The sequence must be ≤ shelf count at each position.
• O(n²) DP without stack optimization: Without the monotonic stack, finding the best left endpoint for each right is O(n), giving O(n²) overall — too slow for large inputs.

Interview preparation tip

For the Array Monotonic Stack Stack Dynamic Programming interview pattern, this problem exemplifies the "stack-optimized DP" technique. When a DP transition requires finding the best left boundary satisfying a monotone condition, a monotonic stack achieves this in amortized O(1) per step. Practice this on simpler variants before attempting this problem.