Maximum Number of Books You Can Take

Problem Statement

In this challenge, you are provided with an array books representing the number of books on each shelf of a bookshelf, indexed from 0 to n-1. The task is to select books from a contiguous subset of shelves, denoted by indices l to r, such that for each shelf i in the range l to r - 1, the number of books you take from shelf i must be strictly less than the number taken from shelf i + 1.

Your goal is to determine the maximum total number of books you can collect under these constraints.

Examples

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.
Total = 1 + 2 + 7 + 9 = 19.

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.
Total = 3 + 4 + 5 = 12.

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.
Total = 1 + 2 + 3 + 7 = 13.

Constraints

• 1 <= books.length <= 10⁵
• 0 <= books[i] <= 10⁵

Approach and Intuition

The core challenge is to find a contiguous subarray in which we can select books in strictly increasing quantities, such that the selected quantity from each shelf does not exceed the shelf's available books.

To maximize the total number of books taken:

1. Use a Stack or Monotonic Pattern:

   • Iterate backward through books, maintaining a stack to simulate increasing sequences from right to left.
   • Greedily attempt to take as many books as allowed while ensuring the strictly increasing constraint.

2. Greedy Backward Sweep:

   • Let books[i] be the current shelf.
   • Keep track of the maximum number of books you are allowed to take at this position (limit). Start with infinity.
   • At each step, set take = min(books[i], limit).
   • Accumulate the total and update limit = take - 1.
   • Stop when limit == 0.

3. Slide Over All Endpoints:

   • Try each possible endpoint r from right to left and simulate collecting books backward to some l, computing the total for that range.
   • Keep track of the maximum total found over all iterations.

This strategy ensures we explore all valid ranges efficiently and find the one that yields the highest number of books under the increasing constraint.

Time Complexity

• The algorithm runs in O(n) due to linear traversal and greedy bookkeeping, suitable for the constraint n <= 10⁵.

Solutions

class Solution {
public:
    long long getMaxBooks(vector<int>& shelf) {
        int len = shelf.size();
    
        // Lambda to compute sum of books between two indices inclusive
        auto calcSum = [&](int start, int end) {
            long long maxCnt = min(shelf[end], end - start + 1);
            return (2 * shelf[end] - (maxCnt - 1)) * maxCnt / 2;
        };
    
        stack<int> indices;
        vector<long long> dp(len);
    
        for (int i = 0; i < len; i++) {
            // Maintain the conditions for the stack
            while (!indices.empty() && shelf[indices.top()] - indices.top() >= shelf[i] - i) {
                indices.pop();
            }
    
            // Calculate dp[i] based on previous values
            if (indices.empty()) {
                dp[i] = calcSum(0, i);
            } else {
                int prev = indices.top();
                dp[i] = dp[prev] + calcSum(prev + 1, i);
            }
    
            // Add current index to stack
            indices.push(i);
        }
    
        // Find the maximum value in dp
        return *max_element(dp.begin(), dp.end());
    }
};