human
I found an interesting problem on https://leetcode.com/problems/longest-well-performing-interval/:
We are given hours, a list of the number of hours worked per day for a given employee.
A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.
A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.
Return the length of the longest well-performing interval.
 
Example 1:
Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

 
Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is the Python program you requested.

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        # Convert array to 0 and 1s
        bits = [1 if x > 8 else -1 for x in hours]
        # Problem becomes: find the longest interval bits[i:j] where sum(bits[i:j]) > 0
        # Get prefix sum of bits
        pref = [0] * (len(bits)+1)
        for i in range(1, len(bits)+1):
            pref[i] = pref[i-1] + bits[i-1]
        # Problem becomes: find the longest interval pref[i:j] where pref[j] > pref[i]
        # Sort index of pref by value. Problem becomes: find the largest sorted_pref[j]-sorted_pref[i] where j > i
        # Greedy to solve the new problem
        ans = 0
        min_val = len(bits) + 1
        for y in sorted(enumerate(pref), key=lambda x: (x[1], -x[0])):
            min_val = min(min_val, y[0])
            ans = max(ans, y[0] - min_val)
        return ans