Problem

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 themaximum number of books you can take from the bookshelf.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8
9

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 <= 10^5
  • 0 <= books[i] <= 10^5

Solution

Method 1 – Monotonic Stack + Dynamic Programming

Intuition

We want to take books from a contiguous segment such that for every shelf, the number of books taken is strictly less than the next shelf. The optimal way is to find, for each position, the best segment ending at that position using a stack to maintain the strictly increasing property efficiently.

Approach

  1. For each shelf, calculate the maximum number of books you can take ending at that shelf.
  2. Use a monotonic stack to keep track of the last shelf where the strictly increasing property would break.
  3. For each shelf, calculate the minimum possible number of books you can take (cannot take more than books[i], and must be less than the next shelf).
  4. Use dynamic programming to store the best result up to each shelf.
  5. Return the maximum value found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    long long maximumBooks(vector<int>& books) {
        int n = books.size();
        vector<long long> dp(n);
        stack<int> st;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && books[st.top()] >= books[i] - (i - st.top())) st.pop();
            int len = st.empty() ? i + 1 : i - st.top();
            long long first = books[i] - len + 1;
            if (first < 0) first = 0;
            long long sum = (first + books[i]) * len / 2;
            dp[i] = sum + (st.empty() ? 0 : dp[st.top()]);
            ans = max(ans, dp[i]);
            st.push(i);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func maximumBooks(books []int) int64 {
    n := len(books)
    dp := make([]int64, n)
    st := []int{}
    var ans int64
    for i := 0; i < n; i++ {
        for len(st) > 0 && books[st[len(st)-1]] >= books[i]-(i-st[len(st)-1]) {
            st = st[:len(st)-1]
        }
        var lenSeg int
        if len(st) == 0 {
            lenSeg = i + 1
        } else {
            lenSeg = i - st[len(st)-1]
        }
        first := books[i] - lenSeg + 1
        if first < 0 {
            first = 0
        }
        sum := int64(first+books[i]) * int64(lenSeg) / 2
        if len(st) == 0 {
            dp[i] = sum
        } else {
            dp[i] = sum + dp[st[len(st)-1]]
        }
        if dp[i] > ans {
            ans = dp[i]
        }
        st = append(st, i)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public long maximumBooks(int[] books) {
        int n = books.length;
        long[] dp = new long[n];
        Deque<Integer> st = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && books[st.peek()] >= books[i] - (i - st.peek())) st.pop();
            int len = st.isEmpty() ? i + 1 : i - st.peek();
            long first = books[i] - len + 1;
            if (first < 0) first = 0;
            long sum = (first + books[i]) * len / 2;
            dp[i] = sum + (st.isEmpty() ? 0 : dp[st.peek()]);
            ans = Math.max(ans, dp[i]);
            st.push(i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maximumBooks(books: IntArray): Long {
        val n = books.size
        val dp = LongArray(n)
        val st = ArrayDeque<Int>()
        var ans = 0L
        for (i in 0 until n) {
            while (st.isNotEmpty() && books[st.last()] >= books[i] - (i - st.last())) st.removeLast()
            val len = if (st.isEmpty()) i + 1 else i - st.last()
            var first = books[i] - len + 1
            if (first < 0) first = 0
            val sum = (first + books[i]).toLong() * len / 2
            dp[i] = sum + if (st.isEmpty()) 0 else dp[st.last()]
            ans = maxOf(ans, dp[i])
            st.addLast(i)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumBooks(self, books: list[int]) -> int:
        n = len(books)
        dp = [0] * n
        st = []
        ans = 0
        for i in range(n):
            while st and books[st[-1]] >= books[i] - (i - st[-1]):
                st.pop()
            length = i + 1 if not st else i - st[-1]
            first = books[i] - length + 1
            if first < 0:
                first = 0
            total = (first + books[i]) * length // 2
            dp[i] = total + (0 if not st else dp[st[-1]])
            ans = max(ans, dp[i])
            st.append(i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn maximum_books(books: Vec<i32>) -> i64 {
        let n = books.len();
        let mut dp = vec![0i64; n];
        let mut st = Vec::new();
        let mut ans = 0i64;
        for i in 0..n {
            while let Some(&last) = st.last() {
                if books[last] >= books[i] - (i as i32 - last as i32) {
                    st.pop();
                } else {
                    break;
                }
            }
            let len = if st.is_empty() { i + 1 } else { i - st.last().unwrap() };
            let mut first = books[i] - len as i32 + 1;
            if first < 0 { first = 0; }
            let sum = (first + books[i]) as i64 * len as i64 / 2;
            dp[i] = sum + if st.is_empty() { 0 } else { dp[*st.last().unwrap()] };
            ans = ans.max(dp[i]);
            st.push(i);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximumBooks(books: number[]): number {
        const n = books.length;
        const dp = new Array(n).fill(0);
        const st: number[] = [];
        let ans = 0;
        for (let i = 0; i < n; i++) {
            while (st.length && books[st[st.length - 1]] >= books[i] - (i - st[st.length - 1])) st.pop();
            const len = st.length === 0 ? i + 1 : i - st[st.length - 1];
            let first = books[i] - len + 1;
            if (first < 0) first = 0;
            const sum = (first + books[i]) * len / 2;
            dp[i] = sum + (st.length === 0 ? 0 : dp[st[st.length - 1]]);
            ans = Math.max(ans, dp[i]);
            st.push(i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each index is pushed and popped from the stack at most once.
  • 🧺 Space complexity: O(n), for the dp array and stack.