Box Office Remittance Bundles
Minimum sum of maxima when partitioning an array into k contiguous groups
A theater box office has an ordered ledger of ticket remittances. Each entry has a nonnegative processing fee recorded in fees.
The ledger must be divided into exactly bundle_count nonempty, contiguous bundles. Every entry must belong to one bundle, and entries cannot be reordered.
The payment processor charges each bundle only the largest processing fee among its entries. The total charge is the sum of these bundle charges.
Return the smallest possible total charge.
Examples
Example 1
Input: fees = [7,2,5,10,1], bundle_count = 2 Output: 11
For fees [7, 2, 5, 10, 1] and two bundles, an optimal division places the first four entries together and the final entry alone. The bundle charges are determined by 10 and 1.
Example 2
Input: fees = [4,4,4,4], bundle_count = 3 Output: 12
All four entries have the same fee. Any division into three nonempty bundles gives the same charge, because each bundle has maximum fee 4.
Constraints
- 1 <= fees.length <= 3000
- 0 <= fees[i] <= 1000000
- 1 <= bundle_count <= min(40, fees.length)
The intended solution takes O(bundle_count * fees.length) time and O(fees.length) auxiliary space. All arithmetic fits exactly in standard JavaScript numbers.
Hints
Show hint 1Hint 1
Let dp[g][i] be the minimum charge for dividing the first i entries into exactly g bundles. A direct transition considers every possible start of the final bundle.
Show hint 2Hint 2
When a new fee is appended, many possible final bundles acquire the same maximum. Use a decreasing stack to merge these candidates, retaining their smallest previous-partition cost and the best total cost across stack groups.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return one optimal list of bundle boundaries?
- How would the dynamic programming change if each bundle were required to contain between L and R entries?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem