There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

&nbsp;
Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.


Example 2:

Input: customers = [1], grumpy = [0], minutes = 1
Output: 1


&nbsp;
Constraints:


	n == customers.length == grumpy.length
	1 &lt;= minutes &lt;= n &lt;= 2 * 104
	0 &lt;= customers[i] &lt;= 1000
	grumpy[i] is either 0 or 1.


class Solution:
    def recursion(self,index,used):
        # base case
        if index == self.n: return 0
        
        #check in dp
        if (index,used) in self.dp: return self.dp[(index,used)]
        #choice1 is using the secret technique
        choice1 = -float('inf')
        
        # we can only use secret technique once and consecutively
        if used == True :
            # use the secret technique
            end = index + self.minutes if index + self.minutes < self.n else self.n
            to_substract = self.prefix_sum[index - 1] if index != 0 else 0
            val = self.prefix_sum[end - 1] - to_substract
            choice1 = self.recursion(end,False) + val
        
        # Do not use the secret tehcnique and play simple 
        choice2 = self.recursion(index+1,used) + (self.customers[index] if self.grumpy[index] == 0 else 0)
        ans = choice1 if choice1 > choice2 else choice2
        
        # Memoization is done here
        self.dp[(index,used)] = ans
        return ans
    
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        self.n = len(customers)
        self.customers = customers
        self.grumpy = grumpy
        self.minutes = minutes
        self.dp = {}
        self.prefix_sum = [x for x in customers]
        for i in range(1,self.n): self.prefix_sum[i] += self.prefix_sum[i-1]
        return self.recursion(0,True)
        
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int start = -1;
        int count = 0;
        
        int max = 0;
        int curr = 0;
        
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                count += customers[i];
            } else {
                curr += customers[i];
            }
            
            if (i-start > minutes) {
                start++;
                if (grumpy[start] == 1) {
                    curr -= customers[start];
                }
            }
            max = Math.max(max, curr);
        }
        
        return count + max;
    }
}
/*
    https://leetcode.com/problems/grumpy-bookstore-owner/
    
    TC: O(N)
    SC: O(1)
    
    Looking at the problem, main thing to find is the window where the minutes should
    be used so that the owner is not grumpy and max customers in that window can be satisifed.
    
    Find the window with most no. of satisfied customers given the owner was originally grumpy but
    now has become not grumpy.
    Since the owner can only be not grumpy for minutes duration, this sets our window size as well.
    So with 'minutes' window size, find the max window.
    
    Then add the max window value with the normal satisfied customers.
*/
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        // Tracks the max window where being not grumpy will add most customers and current grumpy window customers
        int max_grumpy_window = 0, grumpy_window = 0;
        int curr = 0, n = customers.size();
        // Total satisifed customers when owner is not grumpy
        int satisfied_cx = 0;
        // net effective duration of not being grumpy
        minutes = min(minutes, n);
        
        // process the 1st window
        while(curr < minutes) {
            satisfied_cx += (!grumpy[curr] ? customers[curr] : 0);
            grumpy_window += (grumpy[curr] ? customers[curr] : 0);
            ++curr;
        }
        
        max_grumpy_window = max(max_grumpy_window, grumpy_window);
        // process the remaining windows
        while(curr < n) {
            // Remove the 1st element of last window
            grumpy_window -= (grumpy[curr - minutes] ? customers[curr - minutes] : 0);
            // Add the latest element of current window
            grumpy_window += (grumpy[curr] ? customers[curr] : 0);
            max_grumpy_window = max(max_grumpy_window, grumpy_window);
            
            satisfied_cx += (!grumpy[curr] ? customers[curr] : 0);
            ++curr;
        }
        
        return satisfied_cx + max_grumpy_window;
    }
};
var maxSatisfied = function(customers, grumpy, minutes) {
    let left=0;
    let maxUnsatisfied=0;
    let curr=0;
    let satisfied=0;
    
	// finding the satisfied customers
    for(let i=0;i<customers.length;i++){
        if(grumpy[i]===0)satisfied+=customers[i];
    }
    
    // finding the maximum un-satisfied customers within the give timeframe
	// classic sliding window approach
    for(let i=0;i<customers.length;i++){
        if(grumpy[i]) curr+=customers[i];
        if(i-left+1>minutes){
            if(grumpy[left])curr-=customers[left]
            left++
        }   
        if(i-left+1===minutes){
            if(curr>max){
                maxUnsatisfied=curr
            }
        }
    }
	
    return satisfied + maxUnsatisfied;
};
Grumpy Bookstore Owner