I Simply love this Problem

I simply love this problem. It has a simple statement and a simple solution and that enhances all the beauty in it. Ah!! nice way to start the blog in the new year. Wish this we have more and more complex beautiful problems to solve this year.

The problem statement is as follows:

Suppose that each row of an n x n array consists of 1's and 0's such that, in any row of A, all the 1's come before any of the 0's in that row. Describe a method to identify the row which has maximum number of 1's. Fairly straightforward right.

Yes, indeed it is. Now the catch here is you have to solve the above problem in O(n) time and not O(n²) time. This calls for some amount of thinking. All you algorithm buffs, this is not for you. I know this was the thing you solved first in the first course on algorithms.