Maximum number of books you can take

Array Dynamic Programming Stack Monotonic Stack

39.5% acceptance

Mar 31, 2026

296

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_books(books: Vec<i32>) -> i64 {
    // Monotonic stack approach
    // For each position i, we take books[i] books from shelf i.
    // Going left, we take books[i]-1, books[i]-2, ... but capped at books[j].
    // dp[i] = max books ending at i
    // Use stack to find the previous position j where books[j] < books[i] - (i - j)
    // i.e., books[j] - j < books[i] - i
    let n = books.len();
    let mut dp = vec![0i64; n];
    let mut stack: Vec<usize> = Vec::new();
    
    let mut ans = 0i64;
    for i in 0..n {
      let bi = books[i] as i64;
      // Pop stack while books[j] - j >= books[i] - i
      while let Some(&j) = stack.last() {
        if books[j] as i64 - j as i64 >= bi - i as i64 {
          stack.pop();
        } else {
          break;
        }
      }
      
      if let Some(&j) = stack.last() {
        // From j+1 to i, we can take arithmetic sequence ending at books[i]
        let len = (i - j) as i64;
        // Sum = books[i] + (books[i]-1) + ... + (books[i]-len+1)
        // but capped at 0 (can't take negative books)
        let first = bi - len + 1;
        if first > 0 {
          // sum of arithmetic sequence from first to bi
          dp[i] = dp[j] + (first + bi) * len / 2;
        } else {
          // Some shelves contribute 0. The positive part is from 1 to bi.
          // Number of positive terms: bi (values 1, 2, ..., bi)
          dp[i] = dp[j] + bi * (bi + 1) / 2;
        }
      } else {
        // No previous boundary, take from start
        let len = (i + 1) as i64;
        let first = bi - len + 1;
        if first > 0 {
          dp[i] = (first + bi) * len / 2;
        } else {
          dp[i] = bi * (bi + 1) / 2;
        }
      }
      
      ans = ans.max(dp[i]);
      stack.push(i);
    }
    
    ans
  }
}