864. The Longest Stretch In the Black

A log lists the hours worked on each of n days. A day is LONG if more than 8 hours were worked, and SHORT otherwise. A stretch of consecutive days is IN THE BLACK when it holds strictly more long days than short days.

Print the length of the longest stretch in the black, or 0 if there is none.

9 9 6 -> 3 6 6 6 6 6 -> 0 9 9 9 9 6 6 6 6 -> 7

Exactly 8 hours is NOT long, which is the first thing to get right.

## Turning the condition into a prefix sum

Score a long day +1 and a short day -1. Let pre[0] = 0 and pre[i+1] = pre[i] + score(i). A stretch [l, r] is in the black exactly when

pre[r+1] - pre[l] > 0 that is pre[r+1] > pre[l]

So the question becomes: over the n + 1 prefix values, find the largest j - i with i < j and pre[j] > pre[i].

## Why the useful left ends form a decreasing sequence

A left end i is only worth keeping if no earlier index has a prefix value that is smaller or equal, because an earlier index with a value at most pre[i] is better on both counts: it accepts every j that i accepts, and it is further away so the answer is longer.

So build a stack by sweeping i from 0 to n and pushing i only when the stack is empty or pre[i] is strictly below the value at the current top. The stack then holds indices in increasing order with strictly DECREASING prefix values, and those are the only left ends that can ever win.

## The second sweep

Now walk j from n down to 0. While the top of the stack has pre[top] < pre[j], that top is matched with j, the answer j - top is recorded, and the top is popped.

Popping is safe because j is the LARGEST remaining right end for that left end: any j still to come is smaller, so it can only give a shorter answer. The entry has been used to its best advantage and is finished.

That argument is the same domination argument as the rest of the topic, run in the opposite direction: the stack is built left to right and drained right to left.

## Why the strict comparisons matter

The condition is "strictly more long days than short", so the test is pre[j] > pre[i] and never >=. Build the stack with a strict < as well, since an equal prefix value further right is never better. The row 9 9 9 9 6 6 6 6 balances to exactly zero over the whole length and must answer 7, not 8; that single test catches both loosened operators.

## Related problems

Problem 477 asks the mirror question, the widest pair with a[i] <= a[j], and lives under linear dynamic programming. The prefix-sum reformulation is what turns a counting condition into that shape, and it is the step worth remembering.

## Cost

Time O(n), one pass to build the stack and one to drain it. Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ hours[i] ≤ 16` - a day is long when the hours are strictly greater than 8