1124. The longest period of performance One question daily

topic：

1124. The longest period of performance.md

Thought：

This question is not，I thought it was a double pointer but timeout over time，结果是Prefix and算法。The following isSpiritual godSolution
通过Prefix and，我们可以把Elements and elements of sub -array转换成两个Prefix and的差，Right now
$$
\sum_{j=left}^{right} nums[j] = \sum_{j=0}^{right} nums[j]− \sum_{j=0}^{left-1} nums[j]=s[right+1]−s[left]
$$
Now that I said it「Elements and elements of sub -array」，那么利用Prefix and s，Turn the problem to：
Find two bidding i and j，satisfy j<ij<ij<i and s[j]<s[i]，maximize i−jValue。

Code：

Double pointer

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = 0
        for index, i in enumerate(hours):
            count = 0
            j = index
            while j < len(hours):
                if hours[j] <= 8:
                    count -= 1
                elif hours[j] > 8:
                    count += 1
                if count > 0:
                    ans = max(ans, j - index + 1)
                j += 1
        return ans

Prefix and

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        s = [0] * (n + 1)
        st = [0]
        for j, h in enumerate(hours, 1):
            s[j] = s[j - 1] + (1 if h > 8 else -1)
            if s[j] < s[st[-1]]:
                st.append(j)
        ans = 0
        for i in range(n, 0 , -1):
            while st and s[i] > s[st[-1]]:
                ans = max(ans, i-st.pop())
        return ans