Skip to content

2355. Maximum Number of Books You Can Take πŸ”’

DifficultyHard

Description

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 <= 105
  • 0 <= books[i] <= 105

Solutions

Solution 1: Monotonic Stack + Dynamic Programming

Thinking

Books come from a contiguous range of shelves, decreasing by at least one toward the left. Finding the break by brute force for every right end is too slow.

Let \(nums[i]=books[i]-i\). The break is the nearest smaller \(nums[j]\) on the left. A monotonic stack fills \(left[i]\); \(dp[i]\) is the best take ending at \(i\): an arithmetic segment in the middle plus \(dp[j]\) on the left.

Let \(dp[i]\) be the maximum number of books taken from a contiguous segment that ends at shelf \(i\). Set \(nums[i] = books[i] - i\). If the strictly decreasing pattern breaks at some \(j\) with \(0 \le j < i\), then \(books[j] < books[i] - (i - j)\), that is \(nums[j] < nums[i]\). A monotonic stack finds, for each index, the nearest strictly smaller \(nums\) on the left and stores it as \(j\). When no such index exists, \(j = -1\).

The books taken from shelf \(j + 1\) through \(i\) form an arithmetic sequence with difference \(1\). Its length is \(cnt = \min(books[i], i - j)\), it ends at \(books[i]\), and it starts at \(u = books[i] - cnt + 1\). The sum of that sequence is \(s = (u + books[i]) \times cnt / 2\). Then \(dp[i] = s\), plus \(dp[j]\) when \(j \ne -1\).

The answer is \(\max\limits_{i} dp[i]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of \(books\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maximumBooks(self, books: List[int]) -> int:
        nums = [v - i for i, v in enumerate(books)]
        n = len(nums)
        left = [-1] * n
        stk = []
        for i, v in enumerate(nums):
            while stk and nums[stk[-1]] >= v:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        ans = 0
        dp = [0] * n
        dp[0] = books[0]
        for i, v in enumerate(books):
            j = left[i]
            cnt = min(v, i - j)
            u = v - cnt + 1
            s = (u + v) * cnt // 2
            dp[i] = s + (0 if j == -1 else dp[j])
            ans = max(ans, dp[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
33
34
class Solution {
    public long maximumBooks(int[] books) {
        int n = books.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = books[i] - i;
        }
        int[] left = new int[n];
        Arrays.fill(left, -1);
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                left[i] = stk.peek();
            }
            stk.push(i);
        }
        long ans = 0;
        long[] dp = new long[n];
        dp[0] = books[0];
        for (int i = 0; i < n; ++i) {
            int j = left[i];
            int v = books[i];
            int cnt = Math.min(v, i - j);
            int u = v - cnt + 1;
            long s = (long) (u + v) * cnt / 2;
            dp[i] = s + (j == -1 ? 0 : dp[j]);
            ans = Math.max(ans, dp[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
using ll = long long;

class Solution {
public:
    long long maximumBooks(vector<int>& books) {
        int n = books.size();
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) nums[i] = books[i] - i;
        vector<int> left(n, -1);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[stk.top()] >= nums[i]) stk.pop();
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        vector<ll> dp(n);
        dp[0] = books[0];
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            int v = books[i];
            int j = left[i];
            int cnt = min(v, i - j);
            int u = v - cnt + 1;
            ll s = 1ll * (u + v) * cnt / 2;
            dp[i] = s + (j == -1 ? 0 : dp[j]);
            ans = max(ans, dp[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
33
34
func maximumBooks(books []int) int64 {
    n := len(books)
    nums := make([]int, n)
    left := make([]int, n)
    for i, v := range books {
        nums[i] = v - i
        left[i] = -1
    }
    stk := []int{}
    for i, v := range nums {
        for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            left[i] = stk[len(stk)-1]
        }
        stk = append(stk, i)
    }
    dp := make([]int, n)
    dp[0] = books[0]
    ans := 0
    for i, v := range books {
        j := left[i]
        cnt := min(v, i-j)
        u := v - cnt + 1
        s := (u + v) * cnt / 2
        dp[i] = s
        if j != -1 {
            dp[i] += dp[j]
        }
        ans = max(ans, dp[i])
    }
    return int64(ans)
}

Comments