（Monge阵列）对一个
的实数阵列A，若对所有满足
的i,j,k和l有
则称A是Monge阵列（monge array）。换句话说，无论何时选出Monge阵列的两行和两列，对于交叉点上的四个元素，左上和右下两个元素之和总小于等于左下和右上元素之和。
例如，下面就是一个Monge阵列：
10 17 13 28 23
17 22 16 29 23
24 28 22 34 24
11 13 6 17 7
45 44 32 37 23
36 33 19 21 6
75 66 51 53 34
a.证明：一个数组是Monge阵列当且仅当对所有i=1,2,...,m-1和j=1,2,...,n-1，有
（提示：对于“当”的部分，分别对行和列使用归纳法）
b.下面数组不是Monge阵列。改变一个元素使其变成Monge阵列。（提示：利用（a）的结果）
37 23 22 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
c.令f(i)表示第i行的最左最小元素的列下标。证明：对任意的Monge阵列，%5Cleq%20f(2)%20%5Cleq%20...%5Cleq%20f(m))
。
d.下面是一个计算的Monge阵列A每一行最左最下元素的分治算法的描述：
提取A的偶数行构造其子矩阵A'。递归地确定A'每行的最左最小元素。然后计算A的奇数行的最左最小元素。
解释如何在O(m+n)时间内计算A的奇数行的最左最小元素（在偶数行的最左最小元素已知的情况下）。
e.给出（d）中描述的算法的运行时间的递归式。证明其解为O(m+nlgm)。
