Intuition

Not grumpy for minutes consecutive minutes, we need to subtract the previous satisfaction if they were grumpy.

Approach

1. Add the satisfaction from non-grumpy as the base satisfaction.
2. Compute the grumpy satisfaction then we have to make sure we can find the maximum satisfaction in the consecutive minutes.
3. If the current iteration is greater than the minutes and the previous iteration was grumpy, we need to subtract the previous satisfaction.
4. Make sure the satisfaction with Secret Technique is the maximum satisfaction.
5. Return the sum of the base satisfaction and the maximum satisfaction with Secret Technique.

if i >= minutes && grumpy[i-minutes] == 1 {
    satisfiedWithTech -= customers[i-minutes]
}

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

Golang

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
	baseSatisfied        := 0
	satisfiedWithTech    := 0
	maxSatisfiedWithTech := 0

	for i := 0; i < len(customers); i++ {
		if grumpy[i] == 1 {
			satisfiedWithTech += customers[i]
		} else {
			baseSatisfied += customers[i]
		}

		if i >= minutes && grumpy[i-minutes] == 1 {
			satisfiedWithTech -= customers[i-minutes] // because not grumpy for minutes consecutive minutes
		}

		if satisfiedWithTech > maxSatisfiedWithTech {
			maxSatisfiedWithTech = satisfiedWithTech
		}
	}

	return baseSatisfied + maxSatisfiedWithTech
}