Pooled Pickup Release Credits
Maximum score from removing uniform array blocks with weighted squared lengths
A ride-sharing app keeps pending pickup requests in an ordered staging queue. Each request has a pickup-zone ID, given by zones.
The app may repeatedly release a nonempty contiguous block of requests that all have the same zone ID. If a released block contains k requests from zone z, it earns credits[z] * k * k consolidation credits.
Released requests disappear immediately. The remaining requests close the gaps while preserving their relative order, so requests that were previously separated can become adjacent. A release may use any eligible block; it does not have to include every request in its current same-zone run.
Return the maximum total consolidation credits obtainable by releasing every request. An empty queue earns zero credits.
Examples
Example 1
Input: zones = [0,0,1,0], credits = [2,3] Output: 21
Releasing the middle zone-1 request first makes all three zone-0 requests adjacent. They can then be released together, earning a larger zone-0 reward than releasing the two original zone-0 blocks separately.
Example 2
Input: zones = [1,1,1,1], credits = [5,2] Output: 32
The queue has only one zone. Releasing all four requests together maximizes the quadratic reward.
Example 3
Input: zones = [0,1,0,1], credits = [1,10] Output: 42
The zone-1 credit rate is much larger than the zone-0 rate. Removing the intervening zone-0 request allows the two zone-1 requests to be released together.
Constraints
- 0 <= zones.length <= 90
- 1 <= credits.length <= 8
- 0 <= zones[i] < credits.length
- 1 <= credits[z] <= 1000
- All zone IDs and credit rates are integers.
The intended solution uses interval dynamic programming with an additional carried-count state. Its worst-case bounds are O(n^4) time and O(n^3) space. Positive quadratic rewards allow adjacent equal-zone requests at an endpoint to be treated as a single carried group. All answers fit exactly in JavaScript's integer representation.
Hints
Show hint 1Hint 1
An interval alone does not describe every useful subproblem: some matching requests outside it may already be reserved to join an endpoint.
Show hint 2Hint 2
Track how many requests matching the right endpoint are carried into a subproblem. Either release that endpoint group now, or clear an intervening interval so it can join an earlier matching request.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one optimal sequence of releases using the original request indices?
- If the block reward were credits[z] * k instead of credits[z] * k * k, how would the problem simplify?
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