Big Wins! (easy version)

We need maximize

$$\text{med}(a[l,r]) - \min(a[l,r]).$$

The annoying part is the median. The minimum is chill: if we decide the minimum is $m$, then the subarray must contain at least one $m$ and no value smaller than $m$.

The median has a standard trick.

For a candidate value $x$, define

$$b_i = \begin{cases} +1 & a_i \ge x,\\ -1 & a_i < x. \end{cases}$$

For a subarray of length $k$, its upper median is at least $x$ iff at least half of its elements are $\ge x$. With this problem's median definition, that is exactly:

$$\sum b_i \ge 0.$$

For even length, a tie is enough. For odd length, the sum cannot be $0$, so $\ge 0$ still means positive. Nice little parity freebie.

So the problem becomes:

For some minimum $m$ and median threshold $x$, does there exist a subarray such that:

• every element is $\ge m$,
• at least one element is exactly $m$,
• using $+1$ for elements $\ge x$ and $-1$ otherwise, the subarray sum is $\ge 0$?

If yes, then answer can be at least $x-m$.

Because this is the easy version, $a_i \le 100$. So we can simply try all $m$ and $x$. That's only $100^2$ pairs. The only thing we need is an $O(n)$ check per pair that is not stupidly complicated.

Checking one pair $(m,x)$

Elements smaller than $m$ are forbidden, so they split the array into segments. We scan left to right and reset whenever $a_i < m$.

Inside a valid segment, define prefix sum $pref$ over the transformed values:

$$+1 \text{ if } a_i \ge x, \quad -1 \text{ otherwise.}$$

We need a subarray ending at the current position with sum $\ge 0$ and containing at least one $m$.

Suppose the subarray is $(j+1, \dots, i)$. Its sum is

$$pref_i - pref_j.$$

We want this to be nonnegative, so we want a small earlier prefix $pref_j$. But there is also the “must contain an $m$” condition.

When we see an element $a_i=m$, then any future subarray that starts before or at this position and ends later will contain an $m$. So before adding this element, we take the best prefix available so far and mark it as eligible.

More concretely while scanning a segment:

• pref = current prefix sum,
• bestPrefix = minimum prefix sum seen so far in this segment,
• bestWithM = minimum prefix sum among starts that would make the chosen subarray contain an $m$.

At each position:

1. If $a_i=m$, then a subarray starting after any previous prefix and ending at or after $i$ can include this $m$, so update $$bestWithM = \min(bestWithM, bestPrefix).$$
2. Add this element's $+1/-1$ contribution to pref.
3. If $$pref - bestWithM \ge 0,$$ then we found a valid subarray.
4. Update $$bestPrefix = \min(bestPrefix, pref).$$

That is the whole check. No median sorting, no cursed subarray enumeration.

Complexity

There are at most $100$ possible values for $m$ and $100$ possible values for $x$. Each check is $O(n)$.

So the total complexity is

$$O(100^2 \cdot n),$$

which is totally fine for the easy version because the value cap is tiny and the scan is extremely simple. Memory usage is $O(1)$ besides the input array.

One small optimization: only try $x>m$, since $x-m\le 0$ cannot improve the answer. The answer is always at least $0$ from any length-$1$ subarray.