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.

&nbsp;
Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].


Example 2:

Input: hours = [6,6,6]
Output: 0


&nbsp;
Constraints:


	1 &lt;= hours.length &lt;= 104
	0 &lt;= hours[i] &lt;= 16


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        #accumulative count
        #+1 when > 8, -1 when less than 8. 
        #find strictly increasing length.
        
        p = [] #number of tiring days vs not
        c = 0
        for e in hours:
            if e > 8:
                c +=1
            else:
                c-=1
            
            p.append(c)
            
            
        
        #for every moment: we want earliest moment which could be positive overall tiring days.
        a = []
        #a is sorted by tiringnes. At day 8 have -2, want earliest point that could get us to at least 1.
        #so up until that point we have -3, -4, etc, and we want earliest out of it to get longest well performing interval. Which is when prefix comes in.
        
        a1 =[]
        for i in range(len(p)):
            a.append([p[i], i])
            a1.append(p[i])
        
        a1.sort() #bisectable list
        a.sort()
        
        prefix = []
        currearly = float('inf')
        for t, day in a:
            currearly = min(currearly, day)
            prefix.append(currearly)
        
        
        res = 0
        
        # print(p)
        
        for i in range(len(hours)):
            if p[i] > 0:
                res = max(res, i + 1) 
            
            else:
                #find earliest 
                #value must be less than -1-p[i] 
                loc = bisect_right(a1, -1+p[i]) #bisect right means anything before this is less than or equals to
                
                
                
                if loc == 0: #the rightmost place to put it is at the beginning...
                    
                    continue
                
                
                else:
                    earliest = prefix[loc - 1]
                    
                    if earliest >= i: continue
                    
                    interval = i - earliest #notice: we're not including the starting index, since its also technically being removed!

                    # print("From day", earliest, "to", i)
                    
                    res = max(res, interval)
        
        
        
        return res
        
        
        
        
// Brute Force Approach : PrefixSum ((Tiring - Non Tiring) Days) + Checking All Sliding Windows (Lengths 1 To n)
// For Longest Well Performing Interval/Window
// T.C. = O(n^2) , S.C. = O(n)
class Solution {
    
    public int longestWPI(int[] hours) {
        int n = hours.length;
        
        int[] prefixSumTiringDaysMinusNonTiringDaysArr = new int[n + 1];
        prefixSumTiringDaysMinusNonTiringDaysArr[0] = 0;
        
        int prefixSumTiringDaysCount = 0;
        int prefixSumNonTiringDaysCount = 0;
        
        for (int i = 0 ; i < n ; i++) {
            int noOfHoursWorkedToday = hours[i];
            
            if (noOfHoursWorkedToday > 8) {
                prefixSumTiringDaysCount++;
            }
            else {
                prefixSumNonTiringDaysCount++;
            }
            
            prefixSumTiringDaysMinusNonTiringDaysArr[i + 1] = prefixSumTiringDaysCount - prefixSumNonTiringDaysCount;
            // System.out.print(prefixSumTiringDaysMinusNonTiringDaysArr[i] + " ");
        }
        // System.out.println(prefixSumTiringDaysMinusNonTiringDaysArr[n]);
        
        int longestLengthOfContinuousPositiveSequence = 0;
        
        for (int currentSlidingWindowLength = 1 ; currentSlidingWindowLength <= n ; currentSlidingWindowLength++) {
            // System.out.print(currentSlidingWindowLength + " - ");
            for (int i = 0 ; i <= n - currentSlidingWindowLength ; i++) {
                int j = i + currentSlidingWindowLength - 1;
                // System.out.print(i + "," + j + " ");
                int currentIntervalNoOfTiringDaysMinusNonTiringDays = prefixSumTiringDaysMinusNonTiringDaysArr[j + 1] - prefixSumTiringDaysMinusNonTiringDaysArr[i];
                if (currentIntervalNoOfTiringDaysMinusNonTiringDays > 0) { // => currentInterval = Well Performing Interval
                    longestLengthOfContinuousPositiveSequence = Math.max(currentSlidingWindowLength, longestLengthOfContinuousPositiveSequence);
                }
            }
            // System.out.println();
        }
        // System.out.println();
        
        int lengthOfLongestWellPerformingInterval = longestLengthOfContinuousPositiveSequence;
        
        return lengthOfLongestWellPerformingInterval;
    }
    
}
class Solution {
public:
	int longestWPI(vector<int>& hours) {
        int n = hours.size();
		int ans = 0;
		int ct = 0;
		unordered_map<int, int> m;
		for (int i = 0; i < n; ++i) {
			if (hours[i] > 8) ct++;
			else ct--;
			if (ct > 0) ans = max(ans, i + 1);
			else {
				if (m.find(ct) == m.end()) m[ct] = i;
				if (m.find(ct - 1) != m.end()) ans = max(ans, i - m[ct - 1]);
			}
		}
		return ans;
	}
};
var longestWPI = function(hours) {
    var dp = new Array(hours.length).fill(0);
    for(i=0;i<hours.length;i++){
       if(dp[i-1]>0 && hours[i]<=8){
            dp[i]=dp[i-1]-1;
            continue;
        }
        let tiring = 0;
        for(j=i;j<hours.length;j++){
            if(hours[j]>8) tiring++;
            else tiring--;
            if(tiring>0) dp[i] = Math.max(dp[i], j-i+1);
        }}
    return Math.max(...dp);
};
Longest Well-Performing Interval