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 $A_i+B_j\geq h$. If the values in a window are sorted as $r_{(1)},\cdots,r_{(w)}$, feasibility is equivalent to $r_{(k)}\geq k$ for every $k$.

Maintain the frequency of $r_i$ in a sliding window. Define $D_k=\#\{i:r_i\leq k\}-k$. All $D_k$ must be non-positive. A segment tree storing the maximum prefix sum of $\mathrm{cnt}_0,\mathrm{cnt}_1-1,\cdots,\mathrm{cnt}_w-1$ supports insertion, deletion, and checking in $O(\log N)$.

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