Maximum Number of Books You Can Take - Practice Coding Problems

Maximum Number of Books You Can Take - Problem

You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the i^th 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.

Input & Output

Example 1 — Basic Case

$ Input: books = [1,2,10,4,5]

› Output: 13

💡 Note: Taking books from shelves 0, 1, and 2: take 1 from shelf 0, 2 from shelf 1, and 10 from shelf 2. Total = 1 + 2 + 10 = 13. The constraint is satisfied: 1 < 2 < 10.

Example 2 — Single Shelf

$ Input: books = [5]

› Output: 5

💡 Note: Only one shelf available, so we take all 5 books from it.

Example 3 — Descending Order

$ Input: books = [10,8,6,4,2]

› Output: 10

💡 Note: Since books are in descending order, we can only take from one shelf to maintain the ascending constraint. Best choice is shelf 0 with 10 books.

Constraints

1 ≤ books.length ≤ 10⁵
0 ≤ books[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,2,10,4,5] represents books on each shelf

Find Best Sequence

Must take strictly increasing amounts from contiguous range

Output Result

Maximum 13 books from positions 0,1,2

Key Takeaway

🎯 Key Insight: Consider each position as a potential peak and extend optimally in both directions

Asked in

G Google 25 f Meta 18 a Amazon 15 Apple 12

The key insight is to consider each position as a potential peak and extend left with decreasing amounts while extending right with all valid books. The optimal approach uses a peak-based strategy to achieve O(n²) time complexity. For each position i, we calculate the maximum books if position i is the peak of an ascending sequence.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Ranges	O(n³)	O(1)	Check every possible contiguous range and find maximum ascending sequence
Monotonic Stack Optimization	O(n)	O(n)	Use monotonic stack to efficiently find optimal ascending sequences

Brute Force - Try All Ranges — Algorithm Steps

Step 1: Try every possible range [l, r]
Step 2: For each range, greedily construct ascending sequence
Step 3: Track maximum books across all valid ranges

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Range

Select a contiguous range [l, r]

Build Sequence

Greedily construct ascending sequence

Track Maximum

Keep track of best result found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* books, int n) {
    int maxBooks = 0;
    
    // Try every possible range [l, r]
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            // Try to construct ascending sequence in range [l, r]
            int total = 0;
            int valid = 1;
            int prevTaken = 0;
            
            for (int i = l; i <= r; i++) {
                // Must take strictly more than previous position
                int minNeeded = i > l ? prevTaken + 1 : 1;
                
                if (books[i] >= minNeeded) {
                    int taken = books[i];  // Take all available books
                    total += taken;
                    prevTaken = taken;
                } else {
                    // Can't maintain ascending property
                    valid = 0;
                    break;
                }
            }
            
            if (valid) {
                maxBooks = max(maxBooks, total);
            }
        }
    }
    
    // Also consider single positions
    for (int i = 0; i < n; i++) {
        maxBooks = max(maxBooks, books[i]);
    }
    
    return maxBooks;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array from JSON format
    int books[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || strcmp(token, "0") == 0) {
            books[n++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(books, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: O(n²) ranges × O(n) to process each range

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Ranges — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler