Daily bit(e) of C++ | Maximum number of books to take
Daily bit(e) of C++ #79, Common interview problem: Maximum number of books to take
Today we will look at a common C++ interview problem: Maximum number of books to take.
Given an array describing the number of books on bookshelves, determine the maximum number of books you can take under the following conditions:
you must take books from a contiguous selection of bookshelves
the number of books you take from each bookshelf must be strictly increasing
For example, for the input {8, 5, 2, 7, 9}, we can take one book from shelf one (zero-indexed), two from shelf two, seven from shelf three, and finally, nine books from shelf four for a total of 19.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/ax53xfKTa.
Solution
The first observation we need to make is that the maximum number of books we can take if we ignore the number of books on the previous bookshelves is simply the series 1 + 2 + 3 + … + n which sums up to n*(n+1)/2.
We might not reach this optimal number because we either run out of bookshelves or run into a bookshelf with fewer books than we would want to take; let’s call these bottlenecks.
There is, however, a nice property here. If we know how many books (at best) we could take if we would end with a bottleneck, we can calculate the result for a bookshelf as n+(n-1)… up to (but not including) the bottleneck plus the number of books we can take ending in the bottleneck.
To put this together, we need to keep track of two pieces of information:
the current bottlenecks
the number of books we can take ending at each index
