Coding questions · Adobe

Maximize pay by flipping k rest days

This question evaluates algorithm design and optimization skills in string processing and combinatorial decision-making, testing how to maximize weighted sequences of workdays under a limited number of flips.

Given integers BasePay and Bonus, a binary string schedule of length n where '1' means work and '0' means rest, and an integer k, you may change up to k zeros to ones. Pay rules: each workday earns BasePay; if day i and day i-1 are both workdays, you earn an additional Bonus for day i. Return the maximum total pay achievable after up to k flips. Describe your algorithm and analyze its time and space complexity.

Maximize Pay by Flipping Rest Days

Choose up to k rest days to work to maximize base pay plus adjacent-work bonuses.

Constraints

schedule contains 0/1

Examples

Example 1

Input: (10, 5, '1010', 1)
Output: 40

Explanation: Flip one rest day to connect work streak.

Example 2

Input: (10, 5, '000', 2)
Output: 25

Explanation: Choose two adjacent workdays.

Hints

Dynamic programming over day, flips used, and whether the previous day is worked.