1052. Grumpy Bookstore Owner

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        """
        1. get min happy customers by default, mark them to -1 
        2. sliding window left - right get the max additional customer
        tc O(N) sc O(1)
        """
        base = 0
        for idx,(c,g) in enumerate(zip(customers,grumpy)):
            if g == 0:
                base+= c
                customers[idx] = -1

        n = len(customers)
        max_c = -1
        l,rest = 0,0
        for r in range(n):
            rest += customers[r] if customers[r]>0 else 0 
            if r >= X-1:
                max_c = max(max_c,rest)
                rest -= customers[l] if customers[l] >0 else 0 
                l += 1
        return base+max_c
                

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        """
        main idea: use idx, X to distinguish which is happy by default and which are not in one round 
        1. get keep accumulate happy score and record potential_happy score if window is within X range 
        2. remove invalid unhappy score when window is out of left edge 
        3. for each customer, check if potential_happy score has reached the max 
        4. return happy score + potential_happy_max 
        tc O(N) sc O(1)
        """
        base=to_happy=max_to_happy = 0
        for idx,(c,g) in enumerate(zip(customers,grumpy)):
            # if g == 0:
            #     base += c
            # else:
            #     to_happy += c
            base += c*(1-g)
            to_happy += c*g
            if idx >= X:
                # remove left most l = idx-X
                to_happy -= customers[idx-X]*grumpy[idx-X] #if grumpy[idx-X] == 1 else 0        
            max_to_happy = max(max_to_happy,to_happy)
        return base + max_to_happy