The best comb

After mastering the challenges of identifying the largest squares and rectangles of zeros in a numerical matrix, a new, more generalized problem has arisen. Given a matrix composed of zeros and ones, the task is to find the optimal "comb" that can be constructed using the zero cells in this matrix. The optimal comb is defined as the one that covers the maximum number of cells in the matrix. A comb link is a non-empty rectangular section of zeros within the matrix, essentially a submatrix with a non-zero area consisting solely of zeros. A $k$-comb is a structure formed by vertically connecting $k$ (0 \leq k \leq m) links. In these links, the left $x$-coordinate must be consistent, adjacent links must have different widths, and all links must collectively form a connected figure. A $0$-comb always exists and has a size of $0$.

The illustration in Figure $\text{1}$ depicts a valid $7$-comb. Although the structure spans $8$ rows, it qualifies as a $7$-comb because the second and third rows from the bottom share the same link (adjacent links must differ in width, but a link can extend over more than $1$ row). The structure in Figure $\text{2}$ is not a valid comb because the left $x$-coordinate of the links does not align. Similarly, the structure in Figure $\text{3}$ is not a valid comb because it is not a contiguous figure. It is noteworthy that the optimal rectangle is equivalent to the best $1$-comb (a comb with a height of $1$ link). Clearly, for each length $k$ in the matrix, one can either identify the best comb or conclude that it does not exist (i.e., the best comb has a size of $0$). For instance, in Figure $\text{4}$, the best $3$-comb is highlighted (non-zero elements in the matrix are marked with $\text{X}$).

Fig. 4

Your task is to determine the largest comb among all $k$-combs that can be constructed on the zero cells of the given matrix (for all $k$ from $0$ to $m$).