Welcome to Subscribe On Youtube

2355. Maximum Number of Books You Can Take

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

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • 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)
    }
    

All Problems

All Solutions