Suppose that each row of an n n array A consists of 1s and 0s such that, in any row of A, all the 1s come before any 0s in that row. Assuming A is already in memory, describe a method running in O(n) time (not O(n^2) time) for finding the row of A that contains the most 1s.

Provide pseudo-code, correctness, and complexity analysis.