C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Tuesday C++ common interview problem: Maximum books Given an array with counts 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 Solve it yourself: https://lnkd.in/eee4xfCA Solution: https://lnkd.in/eCpSSJiP #cpp #cplusplus #coding #programming #dailybiteofcpp
What about scanning backwards? It seems to work: size_t maximum_books(const std::vector<size_t>& shelves) { size_t cMaxCount = 0; for (size_t i = 0; i < shelves.size(); ++i) { size_t cCurCount = shelves[i]; // Scan backwards starting at the current element. for (size_t j = i, cCurTaken = cCurCount; j > 0 && cCurTaken > 1; --j ) { cCurTaken = std::min(shelves[j - 1], cCurTaken - 1); cCurCount += cCurTaken; } if (cCurCount > cMaxCount) { cMaxCount = cCurCount; } } return cMaxCount; }