題目描述
今天秦陋，書店老板有一家店打算試營業(yè) customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會(huì)進(jìn)入書店，所有這些顧客都會(huì)在那一分鐘結(jié)束后離開。
在某些時(shí)候墩虹，書店老板會(huì)生氣。 如果書店老板在第 i 分鐘生氣憨琳，那么 grumpy[i] = 1诫钓，否則 grumpy[i] = 0。 當(dāng)書店老板生氣時(shí)篙螟，那一分鐘的顧客就會(huì)不滿意菌湃，不生氣則他們是滿意的。
書店老板知道一個(gè)秘密技巧遍略，能抑制自己的情緒惧所，可以讓自己連續(xù) X 分鐘不生氣，但卻只能使用一次绪杏。
請(qǐng)你返回這一天營業(yè)下來下愈，最多有多少客戶能夠感到滿意的數(shù)量。
示例：
輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
輸出：16
解釋：
書店老板在最后 3 分鐘保持冷靜蕾久。
感到滿意的最大客戶數(shù)量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
思路分析
1.暴力法(n^2)
運(yùn)用滑動(dòng)窗口的思想势似，雙重遍歷數(shù)組，依次比較，找出最大值履因。
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int n=customers.length;
int k=0;int sum=0;
//沒有秘密武器時(shí)的滿意度
for(int customer:customers){
sum+=customer*(1-grumpy[k++]);
}
int[] dp=new int[n];int max=0;
for(int i=X-1;i<n;i++){
dp[i]=sum;
//依次遍歷
for(int j=i;j>=i-X+1;j--){
if(grumpy[j]==1) dp[i]+=customers[j];
}
max=Math.max(max,dp[i]);
}
return max;
}
}
2.滑動(dòng)窗口優(yōu)化
當(dāng)沒有秘密武器時(shí)障簿，滿意度等于
當(dāng)有秘密武器時(shí)，額外滿意度為
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int n=customers.length;
int sum=0;int k=0;
//沒有秘密武器
for(int customer:customers){
sum+=customer*(1-grumpy[k++]);
}
int increase=0;
//初始increase
for(int i=0;i<X;i++){
increase+=customers[i]*grumpy[i];
}
int max=increase;
//遞推公式
for(int i=X;i<n;i++){
increase+=customers[i]*grumpy[i]-customers[i-X]*grumpy[i-X];
max=Math.max(max,increase);
}
return sum+max;
}
}
