problem:1052. 爱生气的书店老板

思路：假设老板在[i,j]区间可以保持冷静，那么我们可以求[i,j]区间customers的和，再求出[0,i-1]区间和[j+1,n-1]老板冷静时候的customers的和，取个max就是答案。

前缀和解法：

Accode:

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        vector<int>  origin_sum(1,0),sum(1,0);
        int len = grumpy.size();
        for(int i=0;i<len;i++){
            origin_sum.push_back(origin_sum.back()+customers[i]);
            if(grumpy[i]){
                sum.push_back(sum.back());
            }
            else{
                sum.push_back(sum.back()+customers[i]);
            }
        }
        int ans = 0;
        for(int i=0;i+minutes-1<len;i++){
            ans = max(ans,origin_sum[i+minutes]-origin_sum[i]+sum[i]+sum[len]-sum[i+minutes]);
        }
        return ans;
    }
};

时间复杂度：$o(n)$
滑动窗口解法：

1. 老板不生气时的顾客数量之和s0这些顾客可以感到满意。
2. 长度为minutes的连续子数组中，老板生气时的顾客数量之和 s1的最大值maxs1。这些顾客可以感到满意。
   ans = maxs1+s0

Accode:

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int len = customers.size();
        int ans = 0;
        int sum = 0;
        int tem = 0;
        deque<int> deq;
        for (int i = 0; i < len; i++) {
            if (!grumpy[i])
                ans += customers[i];
            if (deq.size() && i - deq.front() + 1 > minutes) {
                tem -= customers[deq.front()];
                deq.pop_front();
            }
            if (grumpy[i]) {
                deq.push_back(i);
                tem += customers[i];
            }
            sum = max(sum, tem);
        }
        return ans + sum;
    }
};

时间复杂度：$o(n)$