Maximum Number of Books You Can Take - Solution & Explanation

Problem 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.