2D sorted array. Element search.

A 2D integer array is such that each row and column in it is in ascending order. How will you search for a specific element in it ?

Clue: A simple implementation in O(m+n) can be done.  

A more complex recursive approach using diagonals as breakpoints of recursion can also the thought off. Basically, recursively spitting a matrix into sub-square matrices for the search on the diagonal. Am yet struggling with the complexity analysis part. 

Rom/Column Inversion

You are given a matrix m*n (need not be square) of positive/negative integers. The only operations permitted are you invert the signs of an entire row or an entire column. And that is counted as one step. The goal is the to reach the maximum sum possible (of all elements) of the matrix with such a series of operations. 

Q. Does the process converge. If yes, then what is the complexity ?

Clue: When would you do such an operation ? And when you do that what happens to the total sum? What is the max sum which can be reached.