An m n array A of real numbers is a Monge array if for all i, j, k, l such that 1 i < k m and 1 j < l n, we have

A[i, j] + A[k, l] A[i, l] + A[k, j].

That is, the four elements at the intersections of any two given rows and two given columns of a Monge array satisfies the following property: the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements.

1, Property of Monge Array

Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove that for any m n Monge array,

f(1) f(2) f(m).

2. Divide-and-Conquer Method

Below is a divide-and-conquer algorithm that computes the left-most minimum element in each row of an m n Monge array A:

S1. Construct a sub-matrix A0 of A consisting of the even-numbered rows of A.

S2. Recursively determine the leftmost minimum for each row of A0 .

S3. Compute the leftmost minimum in the odd-numbered rows of A.

Explain how Step S3 to compute the leftmost minimum in the odd-numbered rows of A can be done in O(m + n) time, given that the leftmost minimum element of the even numbered rows is known.