Katkat
Back

Maximize Earnings by Converting Days Off into Workdays

RampSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.