Think first about how you can verify that a row
i
has the most 1's in
O
(
n
) time.