86. Book Allocation Problem

There are n books with given page counts and m students. Each student is allocated a contiguous, non-empty range of books, every book must be allocated to exactly one student, and each student's total pages should be minimized as evenly as possible. Find the minimum possible value of 'the maximum number of pages assigned to any student', given an optimal allocation.

Input: The first line contains an integer n. The second line contains n space-separated integers, the page counts. The third line contains the integer m, the number of students. Output: Print a single integer - the minimum possible value of the maximum pages assigned to any student.

1 <= m <= n <= 10^4

This is structurally identical to 'Painter's Partition Problem' - recognizing that many real-world-sounding problems reduce to the exact same 'binary search on the answer + greedy contiguous-partition feasibility check' pattern is a valuable, reusable interview skill.

Allocate books (each a contiguous range) among students, minimizing the maximum number of pages any single student has to read. Brute force: Try every possible way of splitting the books into m contiguous groups directly and compute each split's maximum student-pages - this is combinatorially expensive, impractical for larger n. Optimised: Since 'can M pages-per-student be achieved with m or fewer students' is monotonic (larger M is always at least as easy), binary searching on M with an O(n) greedy feasibility check reduces the expensive combinatorial search to O(n log(sum of pages)).

Recursively try every way of cutting the sequence of n books into m contiguous, non-empty groups: for each student in turn, try every possible number of books they could take next while ensuring remaining students still each get at least one book, recurse on the rest, and combine to get the maximum group sum for that split. Take the minimum of these maximum sums over all valid splits explored. Because this explores essentially every composition of n books into m ordered parts, it is combinatorially explosive. Time: O(2^n) Space: O(n)

Define dp[i][j] as the minimum possible 'maximum pages assigned to any student' when the first i books are optimally split among j students. To compute dp[i][j], try every possible position k < i where the j-th student's block could start, and take dp[i][j] as the minimum over k of the larger of dp[k][j-1] and the sum of pages from k+1 to i, using precomputed prefix sums so each such sum is found in O(1). Filling the full table of states, each needing a scan over split points, gives the overall running time. Time: O(n^2 * m) Space: O(n*m)

The answer lies between the single largest book (a lower bound, since that book alone must go to someone) and the total sum of all pages (an upper bound, giving everything to one student). Binary search this range: for a candidate value mid, greedily walk through the books accumulating pages into the current student's pile and start a new student whenever adding the next book would exceed mid, counting how many students this greedy pass needs. If it needs at most m students, mid is feasible and smaller values are tried; otherwise a larger mid is needed. The tightest feasible value found is the answer, and each feasibility check is a single linear pass. Time: O(n log(sum of pages)) Space: O(1)

1. Binary search on the candidate maximum page count M. 2. For a candidate M, greedily check feasibility: assign books to the current student until adding the next book would push their total past M, then start a new student. 3. If the number of students needed is <= m, M is feasible - try a SMALLER M; otherwise, try a LARGER one.

Time: O(n log(sum of all pages)) - each binary search step's greedy check costs O(n). Space: O(1) extra space beyond the input array.

Test m = n (each student gets exactly one book, answer is the largest single book), m = 1 (one student reads everything, answer is the total pages), and n = 10^4 for performance.

Be ready to state the exact search range bounds (from the single largest book's page count, up to the sum of all pages) - both are meaningful, tight starting bounds worth stating explicitly rather than an arbitrary large number.