Grumpy Bookstore Owner

IF
AlgoAxiomStaff Engineers
JSTS
Medium20 mins

A bookstore owner has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array nums where nums[i] is the number of customers that enter at the start of the ith minute, and an integer array grumpy where grumpy[i] is 1 if the owner is grumpy during minute i, and 0 otherwise.

When the owner is not grumpy, the customers are satisfied. When the owner is grumpy, the customers arriving during that minute are not satisfied.

The owner knows a secret technique to suppress grumpiness for minutes consecutive minutes, making all customers during that window satisfied.

Return the maximum number of satisfied customers after using the technique optimally.

Examples

Input: nums = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3

Output: 16

Explanation: The owner uses the technique on the last 3 minutes (indices 5, 6, 7). Always-satisfied customers (grumpy=0): indices 0,2,4,6 → 1+1+1+7 = 10. Extra from suppressing grumpiness at indices 5 and 7: 1+5 = 6. Total = 16.

Input: nums = [1], grumpy = [0], minutes = 1

Output: 1

Explanation: The customer is already satisfied since the owner is not grumpy.

Input: nums = [4,10,10], grumpy = [1,1,0], minutes = 2

Output: 24

Explanation: Always-satisfied: index 2 → 10. Use technique on indices 0,1 → extra 4+10 = 14. Total = 24.

Constraints

  • n == nums.length == grumpy.length
  • 1 <= n <= 2 * 10^4
  • 0 <= nums[i] <= 1000
  • grumpy[i] is 0 or 1
  • 1 <= minutes <= n
Source: Sliding Window pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle