Calculate highest row sum in efficient way

Question

Hi I am trying to solve one problem. I have m*n matrix. It is integer matrix with 0 and 1 only.I want find out row for which sum of all elements will be highest. I solve this with simple solution. I am using 2 for loops and calculating sum of each row. But I want to find more efficient way to do this. Any one have idea about it. I need an optimized solution. Thank you.

Answer 1

Let's consider any two elements in different rows of the matrix. Just pick two, doesn't matter which ones as long as they are not in the same row. Set every other element of the matrix to zero. Then we can choose which row will be the answer by writing 1 in one of our chosen elements and 0 in the other.

What this says to me is that in the worst case, no matter how clever you are, you may have to examine O(m*n) elements of the matrix in order to find the one that has the sole non-zero value. So you can never have a better worst-case running time than O(m*n).

But you can short-circuit the procedure in some cases. Suppose that so far, the highest sum of elements in any row you have examined so far is x. Now you are examining a new row containing n elements. If, by the time you have examined k of those elements, the sum of those k elements is less than x - n + k, then you know for sure that the sum of elements in that row is less than x, and you do not need to look at that row any further.

This algorithm is still O(mn) in the worst case, but under some reasonable assumptions about the contents of the matrix, its mean (average) running time will be less than the naive algorithm applied to the same matrix. It can also be done by parallel processing, although I think this would lead to somewhat more steps (on average), albeit divided over more processors. That is, I'd expect the "speedup factor" to be somewhat less than the number of processors used.