Maximize Earnings by Converting Days Off into Workdays
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Maximize Earnings by Converting Days Off into Workdays
An employee is planning a work schedule for `n` consecutive days. For day `i` you are given whether it is originally a **workday** or a **day off**.
The pay rules are:
- On every day the employee actually works, they earn a fixed amount `wage` dollars.
- On a workday, the employee additionally earns `bonus` dollars **if and only if** the immediately preceding day was also a workday (a "streak" bonus). Day `0` can never earn the streak bonus because it has no preceding day.
The employee may convert **at most `k`** of the original days off into workdays. (Workdays cannot be converted into days off, and converting a day off is optional.)
Return the **maximum total earnings** the employee can achieve over the `n` days after performing at most `k` such conversions.
### Input
- An integer `n` — the number of days.
- An integer `k` — the maximum number of days off that may be converted to workdays (`0 <= k <= n`).
- An integer `wage` — dollars earned for each day worked.
- An integer `bonus` — extra dollars earned on a workday whose previous day was also worked.
- An array `schedule` of length `n` where `schedule[i] == 1` means day `i` is originally a workday and `schedule[i] == 0` means day `i` is originally a day off.
### Output
- A single integer: the maximum total earnings achievable.
### Constraints
- `1 <= n <= 100000`
- `0 <= k <= n`
- `0 <= wage <= 10^4`
- `0 <= bonus <= 10^4`
- `schedule[i] ∈ {0, 1}`
- The answer can exceed 32-bit range; use 64-bit integers.
### Example 1
```
n = 5
k = 2
wage = 10
bonus = 5
schedule = [1, 0, 0, 1, 0]
Output: 55
```
Explanation: Convert the days off at indices `1` and `2`, making the schedule `[1, 1, 1, 1, 0]`. There are `4` workdays earning `4 * 10 = 40`. The consecutive-work pairs are `(0,1)`, `(1,2)`, `(2,3)`, contributing `3 * 5 = 15` in streak bonuses. Total `40 + 15 = 55`. No other choice of at most `2` conversions yields more.
### Example 2
```
n = 4
k = 0
wage = 7
bonus = 3
schedule = [1, 1, 0, 1]
Output: 24
```
Explanation: No conversions are allowed (`k = 0`). The worked days are indices `0`, `1`, `3`, earning `3 * 7 = 21`. The only pair of adjacent worked days is `(0, 1)`, contributing one streak bonus of `3`. Total `21 + 3 = 24`. This confirms the model: `wage` is paid once per worked day, and `bonus` is paid once for each pair of adjacent worked days.
Quick Answer: This question evaluates a candidate's skill in dynamic programming and constrained optimization, specifically deciding which state transitions to modify under a limited budget of changes. It falls under coding and algorithms interviews, testing practical application of greedy or DP reasoning over sequential data with adjacency-based bonuses rather than pure conceptual knowledge.
An employee is planning a work schedule for `n` consecutive days. For day `i` you are given whether it is originally a **workday** or a **day off**.
The pay rules are:
- On every day the employee actually works, they earn a fixed amount `wage` dollars.
- On a workday, the employee additionally earns `bonus` dollars **if and only if** the immediately preceding day was also a workday (a "streak" bonus). Day `0` can never earn the streak bonus because it has no preceding day.
The employee may convert **at most `k`** of the original days off into workdays. (Workdays cannot be converted into days off, and converting a day off is optional.)
Return the **maximum total earnings** the employee can achieve over the `n` days after performing at most `k` such conversions.
### Input
- An integer `n` — the number of days.
- An integer `k` — the maximum number of days off that may be converted to workdays (`0 <= k <= n`).
- An integer `wage` — dollars earned for each day worked.
- An integer `bonus` — extra dollars earned on a workday whose previous day was also worked.
- An array `schedule` of length `n` where `schedule[i] == 1` means day `i` is originally a workday and `schedule[i] == 0` means day `i` is originally a day off.
### Output
- A single integer: the maximum total earnings achievable.
### Constraints
- `1 <= n <= 100000`
- `0 <= k <= n`
- `0 <= wage <= 10^4`
- `0 <= bonus <= 10^4`
- `schedule[i] in {0, 1}`
- The answer can exceed 32-bit range; use 64-bit integers.
### Example 1
```
n = 5, k = 2, wage = 10, bonus = 5, schedule = [1, 0, 0, 1, 0]
Output: 55
```
Convert the days off at indices `1` and `2`, making the schedule `[1, 1, 1, 1, 0]`. Four workdays earn `4 * 10 = 40`; the consecutive-work pairs `(0,1),(1,2),(2,3)` contribute `3 * 5 = 15`. Total `55`.
### Example 2
```
n = 4, k = 0, wage = 7, bonus = 3, schedule = [1, 1, 0, 1]
Output: 24
```
No conversions allowed. Worked days `0,1,3` earn `3 * 7 = 21`; the only adjacent worked pair `(0,1)` adds `3`. Total `24`.
Constraints
- 1 <= n <= 100000
- 0 <= k <= n
- 0 <= wage <= 10^4
- 0 <= bonus <= 10^4
- schedule[i] in {0, 1}
- The answer may exceed 32-bit range; use 64-bit integers.
Examples
Input: (5, 2, 10, 5, [1, 0, 0, 1, 0])
Expected Output: 55
Explanation: Convert indices 1 and 2 -> [1,1,1,1,0]. 4 workdays = 40, pairs (0,1),(1,2),(2,3) = 15. Total 55.
Input: (4, 0, 7, 3, [1, 1, 0, 1])
Expected Output: 24
Explanation: No conversions. Worked days 0,1,3 = 21, only adjacent pair (0,1) adds 3. Total 24.
Hints
- A worked day always contributes `wage`; a bonus is earned once for every pair of adjacent worked days. So total = wage * (#worked days) + bonus * (#adjacent worked pairs).
- Greedy on 'most valuable conversion first' fails because the streak bonus is created by two adjacent days working together — the marginal value of a conversion depends on its neighbors, which other conversions can change.
- Do a DP over days. Track two things at each day: how many conversions you have used so far, and whether the current day ends up worked or not.
- State: dp[i][j][worked]. A day that is originally a workday must stay worked; a day off may be left off, or worked at the cost of one conversion. Add the streak bonus only when transitioning worked -> worked. Keep just the previous day's rows to get O(k) memory.