Largest Rectangle in a Histogram Returns

Fix a width $w$ and a target height $h$. It is sufficient to use the $w$ largest elements of $B$ for the chosen interval. Sort the interval's $A$ values increasingly and those $B$ values decreasingly. The interval is feasible exactly when every paired sum is at least $h$.

For every $A_i$, let $r_i$ be the number of elements $B_j$ satisfying . If the values in a window are sorted as , feasibility is equivalent to for every .

Maintain the frequency of $r_i$ in a sliding window. Define $D_k=\#\{i:r_i\leq k\}-k$. All must be non-positive. A segment tree storing the maximum prefix sum of supports insertion, deletion, and checking in .

For every width $w$, binary-search the largest feasible $h$ and maximize $wh$. The time complexity is $O(N^2\log N\log V)$.