Maximize Earnings by Converting Days Off
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Implement `maximum_schedule_earnings(schedule, k, daily_pay, consecutive_bonus)`.
`schedule[i]` is `1` for an existing workday and `0` for a day off. Every workday earns `daily_pay`. A workday also earns `consecutive_bonus` when the previous calendar day is a workday. You may change at most `k` days off into workdays. Return the maximum total earnings over the entire schedule.
### Constraints
- `1 <= len(schedule) <= 200000`
- `schedule[i]` is `0` or `1`.
- `0 <= k <= len(schedule)`
- `0 <= daily_pay, consecutive_bonus <= 10^9`
- Return a 64-bit integer.
### Examples
- `[1, 0, 1]`, `k = 1`, `daily_pay = 10`, `consecutive_bonus = 5` returns `40` after changing the middle day: three daily payments and two bonuses.
- `[0, 0]`, `k = 1`, `daily_pay = 7`, `consecutive_bonus = 3` returns `7`.
```hint The value of a changed day depends on its neighbors
Joining two work blocks can create two bonuses, while extending one block creates one.
```
```hint Formulate a small-state dynamic program
Process days left to right while tracking changes used and whether the previous day is worked; then look for how to exploit the structure without an `O(nk)` table.
```
Quick Answer: Implement `maximum_schedule_earnings(schedule, k, daily_pay, consecutive_bonus)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Each one in `schedule` is an existing workday and each zero is a day off. A workday earns `daily_pay` plus `consecutive_bonus` when the previous calendar day is also a workday. Change at most `k` days off into workdays and return the maximum total earnings as an exact 64-bit integer.
Constraints
- 1 <= len(schedule) <= 200000 and every schedule value is zero or one.
- 0 <= k <= len(schedule).
- 0 <= daily_pay, consecutive_bonus <= 10^9.
- Return an exact 64-bit integer; all valid results are also exact JavaScript integers below 2^53.
Examples
Input: ([1, 0, 1], 1, 10, 5)
Expected Output: 40
Explanation: Filling the middle day joins both existing work blocks for two bonuses.
Input: ([0, 0], 1, 7, 3)
Expected Output: 7
Explanation: One changed day earns daily pay but no consecutive bonus.
Hints
- Test k = 0, an all-work schedule, an all-off schedule, and a budget larger than the zero count.
- Include changes at the schedule edges and internal gaps of several different lengths.
- Exercise zero daily pay, zero consecutive bonus, and both maximum pay values.