So whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection points, the sum of the upperleft and lower right elements is less than or equal to the sum of the lowerleft and upperright elements.
This array is a Monge array:
For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are:
17 + 7 = 24
23 + 11 = 34
It holds that the sum of the upperleft and lower right elements is less than or equal to the sum of the lowerleft and upperright elements.
Monge arrays are useful for keeping growth of functions in O(nlogn) time or less.
See also:
Search Encyclopedia

Featured Article
