Maximize Pay by Booking Free Days
MediumDynamic Programming ยท Citadel
Given a calendar days, where days[i] is 1 if day i is booked and 0 if it is free, book at most k free days and return the maximum total pay. Booked days stay booked.
Each booked day pays base, plus bonus when the day before it is also booked.
Example 1
- Input:
- days = [1, 0, 0, 1, 0], k = 2, base = 10, bonus = 5
- Output:
- 55
- Explanation
- Booking days 1 and 2 gives four booked days in a row: 4 * 10 plus 3 bonuses of 5.
Example 2
- Input:
- days = [0, 0, 0, 0], k = 2, base = 4, bonus = 3
- Output:
- 11
Example 3
- Input:
- days = [0, 1, 0], k = 5, base = 3, bonus = 1
- Output:
- 11
- Explanation
- Booking both free days is allowed even though k is larger than needed: 3 * 3 plus 2 bonuses.
Constraints
1 <= days.length <= 2000days[i]is0or10 <= k <= days.length1 <= base <= 10000 <= bonus <= 1000