Maximum Number of Books You Can Take

Problem Description

Given an array books where books[i] is the number of books on the iᵗʰ shelf, you must choose a contiguous section of the bookshelf [l, r]. Then, for every shelf in the section (except the rightmost one) you decide on a “take‐amount” x[i] with the restrictions:   • 0 ≤ x[i] ≤ books[i] for every shelf;   • For every index l ≤ i < r, x[i] must be strictly less than x[i+1]. Return the maximum total number of books (sum of x’s) you can take by optimally choosing the section and the amounts. The “take‐amounts” in an optimal solution will always “saturate” at each shelf in the following greedy way: if you fix the right boundary r (where you take books[r] = books[r]), then for every shelf i in [l, r) the optimal choice is   x[i] = min(books[i], x[i+1] - 1) (with the understanding that if at any shelf the computed take becomes < 1, you cannot extend further to the left). For example, if books = [8,5,2,7,9] one optimal solution is to take from shelves 1 to 4 with take amounts [1,2,7,9] which adds up to 19.

Key Insights

• For any contiguous segment [l, r] with r chosen as the right boundary, the greedy optimal strategy is to set x[r] = books[r] and, proceeding backwards, set x[i] = min(books[i], x[i+1] - 1).
• The recurrence forces the “available” amount for shelf i to be at most one less than what was taken from shelf i+1, so the left extension can stop once this value drops below 1.
• The problem reduces to trying every possible right endpoint r and “simulating” backwards as far as possible until the allowed pick is 0.
• Although a naïve two‐loops approach has worst‐case O(n²), many test cases and typical inputs allow this greedy “backward‐simulation” to run fast in practice. (Alternately, one may use more advanced data structures – for example, a monotonic stack or RMQ – to “jump” over segments and achieve an O(n) solution, but the greedy simulation is simple and shows the key idea.)

Space and Time Complexity

Time Complexity: In worst case, O(n²) if every simulation from a right endpoint requires scanning almost the entire prefix. However, with typical inputs (or with additional optimizations) the solution runs efficiently. Space Complexity: O(1) extra space (apart from the input).

Solution

The central idea is that for every possible right endpoint r, we “simulate” the optimal backwards choice for the contiguous segment. Start by setting the take-amount at the right end to books[r]. Then move leftwards and at each shelf i compute take = min(books[i], previous_take - 1). If that computed take is less than 1, we stop. We compute the sum for that segment and update our global best answer. This method uses only a few variables to maintain the current “allowed” value and the running sum. Although in worst-case the nested simulation is quadratic, in practical inputs the average cost is much lower. (There also exists an advanced approach using RMQ/monotonic stack to “jump” many indices at once.)

Code Solutions

Below are code solutions in Python, JavaScript, C++ and Java with line‐by‐line comments.