Question: Given a M*N matrix A in which all the elements in a row and all the elements in a column are strictly increasing. Find a path from the smallest element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum. Time Complexity O(m+n). Use efficient space

Solution: Only two paths are possible either first row and last column or first column and last row(Why?? Think Yourself!!) Calculate sum of these two paths ans select one with less sum. And that can be easily done in O(m+n)