<p>We are given <code>hours</code>, a list of the number of hours worked per day for a given employee.</p>

<p>A day is considered to be a <em>tiring day</em> if and only if the number of hours worked is (strictly) greater than <code>8</code>.</p>

<p>A <em>well-performing interval</em> is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.</p>

<p>Return the length of the longest well-performing interval.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> hours = [6,6,6]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= hours.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= hours[i] &lt;= 16</code></li>
</ul>

class Solution {
public:
    int longestWPI(vector<int>& hours)
    {
        
        map<int,int> mp;
        
        //map<int, int> mp = { {0,-1} }; //{non tiring days - tiring days,  index}
        mp[0] = -1; 
        
        int maxLen = 0, count = 0;
        
        for(int i=0; i<hours.size(); i++)
        {
            count += hours[i] > 8? -1 : 1;
            
            auto it = mp.upper_bound(count);
            
            if(it != mp.end())
            {
                maxLen = max(maxLen,i-it->second);
            }
            else
            {
                mp.insert({count,i});
            }
        }
        
        return maxLen;
    
}
};


 /*Initialization:
cpp
Copy code
map<int, int> mp = { {0, -1} };
A map<int, int> named mp is initialized. The keys of this map will store the difference between non-tiring and tiring days (explained further below). The value stores the first index where this difference occurred.
The pair {0, -1} is initially inserted, meaning before any day has been processed, the count difference (non-tiring days - tiring days) is 0, and this is at a "virtual" index -1 to allow proper subarray calculation starting from index 0.
2. Variables:
cpp
Copy code
int maxLen = 0, count = 0;
maxLen: This stores the length of the longest subarray found where tiring days outnumber non-tiring days.
count: This will be used to keep track of the difference between non-tiring and tiring days as we process the array.
3. Main Loop:
cpp
Copy code
for(int i = 0; i < hours.size(); i++)
{
    count += hours[i] > 8 ? -1 : 1;
This loop processes each element of the hours array.
For each day:
If hours[i] > 8 (tiring day), we subtract 1 from count. This is because tiring days should "decrease" the difference.
If hours[i] <= 8 (non-tiring day), we add 1 to count. This is because non-tiring days should "increase" the difference.
The count value is essentially tracking the difference between the number of non-tiring and tiring days encountered so far. The goal is to find subarrays where count becomes positive, indicating more non-tiring days than tiring.
4. Checking for Valid Subarrays:
cpp
Copy code
auto it = mp.upper_bound(count);
mp.upper_bound(count) searches the map mp for the smallest key greater than count.
Why this works:
A negative count means that up to this point, there have been more tiring days than non-tiring ones. To form a valid subarray, we need to find an earlier point in the array where the count difference was less negative than the current count. This is where upper_bound comes in.
If we find such a previous count difference, the subarray from that earlier index to the current index contains more tiring days than non-tiring days.
5. Updating the Maximum Length:
cpp
Copy code
if(it != mp.end())
{
    maxLen = max(maxLen, i - it->second);
}
If upper_bound(count) found a valid entry in mp (i.e., it != mp.end()), it means there is a previous index where the count difference was less than count. This implies that the subarray from that previous index (it->second) to the current index i has more tiring days than non-tiring days.
The length of this subarray is i - it->second, and we update maxLen accordingly.
6. Inserting into the Map:
cpp
Copy code
else
{
    mp.insert({count, i});
}
If no valid entry was found in the map for the current count (meaning upper_bound(count) didn't find anything greater), we insert {count, i} into the map. This means we're recording the first time we encountered this particular count at index i.
Storing the first occurrence of each count difference is crucial because it helps us find the longest subarrays later.
7. Return the Result:
cpp
Copy code
return maxLen;
After processing all the elements in hours, we return the length of the longest subarray found where tiring days outnumber non-tiring days.
Key Concepts:
Count Calculation: The count keeps track of the balance between non-tiring days and tiring days as we go through the array. A more negative count means more tiring days.

Map: The map mp helps in efficiently finding the first occurrence of each count difference, allowing us to quickly compute subarray lengths.

Upper Bound: The use of mp.upper_bound(count) ensures that we can find the smallest previously seen count that would lead to a valid subarray.*/
26100