Chess Club Ledger Sessions
Minimum peak sum of k contiguous array parts, with lexicographically first cuts
A chess club records one signed rating adjustment after each round. Positive adjustments represent gains, negative adjustments represent losses, and zero represents no change.
The club must divide its chronological ledger into exactly sessions nonempty, consecutive review sessions. Every adjustment must belong to exactly one session. A session's net adjustment is the sum of its entries.
The peak adjustment of a division is the largest net adjustment among its sessions. Find a division with the smallest possible peak adjustment. Negative peak adjustments are allowed.
A cut position c means that one session ends immediately before adjustments[c]: the preceding session includes entries through index c - 1. Thus, the cut positions must be strictly increasing integers between 1 and len(adjustments) - 1.
If multiple divisions attain the minimum peak adjustment, choose the one whose list of cut positions is lexicographically smallest: at the first differing position, the smaller cut wins.
Return an integer list containing the minimum peak adjustment first, followed by the chosen sessions - 1 cut positions. When sessions is 1, return a list containing only the sum of the entire ledger.
Examples
Example 1
Input: adjustments = [6,-8,5,4,-3], sessions = 2 Output: [3,3]
The optimal division places the first three adjustments in one session and the remaining two in the other. A negative adjustment can offset earlier gains within the same session.
Example 2
Input: adjustments = [0,0,0,0,0], sessions = 3 Output: [0,1,2]
Every division has the same peak adjustment because all entries are zero. The tie-breaking rule chooses the earliest possible first cut, followed by the earliest possible second cut.
Example 3
Input: adjustments = [-4,-2,-7,-1], sessions = 2 Output: [-6,2]
All session sums are negative. The largest of those sums is still the peak adjustment, so a value closer to zero is worse than a more negative value.
Constraints
- 1 <= len(adjustments) <= 4000
- -1000000 <= adjustments[i] <= 1000000
- 1 <= sessions <= min(25, len(adjustments))
Use integer arithmetic. The intended solution takes O(n * sessions * log(1 + n * M)) time for binary search, where M is the maximum absolute adjustment, followed by O(n * sessions) reconstruction preprocessing. It uses O(n * sessions) space. Signed entries make a greedy left-to-right capacity check invalid.
Hints
Show hint 1Hint 1
For a proposed peak limit, ask whether exactly the required number of nonempty sessions can each have a sum at most that limit. Feasibility is monotone in the limit, even though individual ledger entries may be negative.
Show hint 2Hint 2
Let prefix[i] be the sum before index i. In one dynamic-programming layer, a reachable earlier boundary j can precede boundary i when prefix[j] >= prefix[i] - limit. As i advances, only the largest eligible reachable prefix is needed. A reverse version can support earliest-cut reconstruction.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct the lexicographically largest optimal cut list instead?
- If all adjustments were nonnegative, which parts of the feasibility algorithm could be replaced by a simpler method?
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