Watch 6 video solutions for Maximum Number of Books You Can Take, a hard level problem involving Array, Dynamic Programming, Stack. This walkthrough by Angshuman Bhowmik has 4,372 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the ith shelf of a bookshelf.
You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.
Return the maximum number of books you can take from the bookshelf.
Example 1:
Input: books = [8,5,2,7,9] Output: 19 Explanation: - Take 1 book from shelf 1. - Take 2 books from shelf 2. - Take 7 books from shelf 3. - Take 9 books from shelf 4. You have taken 19 books, so return 19. It can be proven that 19 is the maximum number of books you can take.
Example 2:
Input: books = [7,0,3,4,5] Output: 12 Explanation: - Take 3 books from shelf 2. - Take 4 books from shelf 3. - Take 5 books from shelf 4. You have taken 12 books so return 12. It can be proven that 12 is the maximum number of books you can take.
Example 3:
Input: books = [8,2,3,7,3,4,0,1,4,3] Output: 13 Explanation: - Take 1 book from shelf 0. - Take 2 books from shelf 1. - Take 3 books from shelf 2. - Take 7 books from shelf 3. You have taken 13 books so return 13. It can be proven that 13 is the maximum number of books you can take.
Constraints:
1 <= books.length <= 1050 <= books[i] <= 105Problem Overview: You are given an array where books[i] represents the number of books on shelf i. You can pick a contiguous segment ending at i, but the number of books you take must strictly decrease by at least 1 as you move left. The goal is to maximize the total books taken.
Approach 1: Brute Force Decreasing Simulation (O(n²) time, O(1) space)
For each index i, treat it as the rightmost shelf of your selection. Move left while enforcing the decreasing rule: if you take x books from shelf i, the next shelf can contribute at most x-1, then x-2, and so on. At each step clamp the value to books[j] and stop when the allowed value becomes zero. Sum the values to compute the best segment ending at i. This direct simulation checks every possible ending position but may scan many shelves repeatedly.
Approach 2: Monotonic Stack + Dynamic Programming (O(n) time, O(n) space)
The optimal solution processes shelves from left to right and uses a monotonic stack to find how far the decreasing sequence can extend. The key observation: if you take books[i] from shelf i, the valid sequence to the left becomes books[i], books[i]-1, books[i]-2.... The smallest index you can extend to depends on when this decreasing pattern violates the actual shelf counts.
Maintain a stack of indices where the value books[i] - i is increasing. This transformation normalizes the decreasing constraint so you can quickly find the previous boundary where the pattern breaks. When processing a new shelf, pop stack elements that violate this condition. The remaining top gives the left boundary of the current valid segment.
Use dp[i] to store the maximum books you can collect for a segment ending at i. Once the boundary is known, compute the contribution of the segment using an arithmetic progression sum: the sequence decreases by 1 per step but cannot exceed the shelf's actual count. Add the previous dp value if the segment connects to an earlier valid block. This avoids recomputing sums and keeps the algorithm linear.
This technique combines Array traversal, Monotonic Stack boundary detection, and Dynamic Programming accumulation. Each index enters and leaves the stack at most once, giving true O(n) complexity.
Recommended for interviews: Interviewers expect the monotonic stack + DP solution. The brute force approach shows you understand the decreasing constraint and segment simulation, but the optimized approach demonstrates pattern recognition, stack-based boundary computation, and efficient arithmetic progression calculations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Decreasing Simulation | O(n²) | O(1) | Good for understanding the decreasing constraint and validating logic during interviews |
| Monotonic Stack + Dynamic Programming | O(n) | O(n) | Optimal approach for large inputs and expected solution in technical interviews |