Region of Twos

A cell satisfies $C_{i,j}=2$ exactly when $A_i=B_j=1$.

Take one consecutive run of ones in $A$ and one consecutive run of ones in $B$. Their Cartesian product forms a rectangular connected component of value-$2$ cells. Different runs are separated by at least one zero, so their corresponding rectangles cannot be connected.

Therefore, if $L_A$ and $L_B$ are the longest consecutive runs of ones in $A$ and $B$, the answer is . Scanning both sequences once takes time.