714. The Longest Run With the Best Bitwise AND

Among all contiguous stretches, consider the LARGEST possible bitwise AND of a stretch's values. Print the length of the longest stretch achieving it.

1 2 3 3 2 2 -> 2 the best AND is 3, achieved by 3 3 1 2 3 4 -> 1 5 5 5 -> 3 4 1 4 4 -> 2

## The best AND is just the largest value

AND never turns a 0 bit into a 1, so adding a value to a stretch can only clear bits:

x & y <= x and x & y <= y for every x, y

So the AND of a stretch is at most its smallest value, and therefore at most the largest value in the whole array. That bound is reached by the single-element stretch holding the maximum.

The best AND is therefore max(a), with no search at all.

Reading a statement carefully enough to see that the expensive-sounding quantity is already known is the entire exercise. This is the same lesson problem 691 teaches with "maximum at most X".

## Which stretches achieve it

A stretch has AND equal to m = max(a) only if every value in it is at least m as a bitmask, and since m is the maximum, every value in it must EQUAL m. So the answer is the longest run of the maximum value:

m = max(a) run = 0; best = 0 for v in a: run = run + 1 if v == m else 0 best = max(best, run)

## Why a window sweep is the wrong instinct here

Maintaining a running AND over a sliding window is awkward, because AND has no inverse and a value leaving cannot be undone. Several problems in this topic work around that: problem 696 gets away with XOR only because its invariant guarantees each bit has one owner.

Here the workaround is not needed at all, and recognising that is worth more than implementing it.

## Boundaries

All values equal answers n. All distinct answers 1. An array containing a zero still answers at least 1, since the maximum is whatever it is.

## Cost

Time O(n). Space O(1).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^6`